Interference-Aware IEEE WiMax Mesh Networks

Presentation on theme: "Interference-Aware IEEE WiMax Mesh Networks"— Presentation transcript:

1 Interference-Aware IEEE 802.16 WiMax Mesh Networks
Vehicular Technology Conference, VTC 2005-Spring IEEE 61st Publication Date: 30 May-1 June 2005 Hung-Yu Wei, Samrat Ganguly, Rauf Izmailov Broadband & Mobile Networking Department NEC Laboratories America Princeton, New Jersey, USA Zygmunt J. Haas School of Electrical and Computer Engineering Cornell University Ithaca, New York, USA Abstract IEEE802.16提供建立能在高速無線廣域網路建置的多點mesh的機制(?)。 為了實現所有潛在的高速IEEE802.16mesh網路，故發展兩種有效的無線頻道資源分配extension。 本篇論文的目的在於提出一有效方法增加wimax的利用率透過適當的routing與scheduling的設計。 當多點傳送造成干擾是wimax的限制因素，我們採用interference-aware cross-layer設計來增加效能。 當scheme建立tree-based routing架構同時scheduling也是interference-aware故能有較高spectral efficiency。 性能衡量顯示proposed能達成顯著的性能enhance在basic的架構上。 Presented by: Chan Chih-Yuan 2019/4/29 OPLAB,NTUIM

2 Outline Section 1. Introduction Section 2. Overview Of Wimax Mesh Mode
Section 3. Interference-Aware Design With Mesh Section 4. Performance Evaluation Section 5. Conclusion 2019/4/29 OPLAB,NTUIM

3 Wide-area wireless backhaul network
Introduction IEEE standard high speed at low cost, and easy to deploy. great wireless coverage of about 5 miles with LOS (line of sight) transmission within bandwidth of up to 70 Mbps. Wide-area wireless backhaul network Increase the wireless coverage Provides features such as lower backhaul deployment cost, rapid deployment, and reconfigurability. Ieee802.16小組提出新標準稱wimax，提供高速低成本易建置，同時也提供可擴充的光纖骨幹延伸解決方案。 有五英哩的無線涵蓋率與頻寬高於70mbps的LOS傳輸。 除了提供single last hop access給寬頻ISP，也可使用於建立Wide-area wireless backhaul network，當backhaul-based Wimax建置於mesh模式 不只能增加無線網路涵蓋率，同時也提供低backhaul建置成本，快速建置與可重配置性。 由於wimax提供multihop mesh架構建置於高速的無線網路環境，故發展出兩種resource allocation 除了singlehop Ieee PMP操作，Ieee802.16a標準定義基本的訊號流與訊息格式來建立mesh網路連線。 結果mesh模式規格被整合進ieee 的revision。雖然singlehop提供高彈性達成資料相關的Qos，但在multihop mesh卻具有挑戰。 其中之一的主要問題在於來自鄰節點傳輸時的干擾。 2019/4/29 OPLAB,NTUIM

4 Cross-layer design and optimization
Application Layer Load Demand Physical Layer Interference Information Scheduling and Route Selection Mechanism in Data Link Layer Interference-Aware IEEE Framework Interference-aware route construction algorithms Enhanced centralized mesh scheduling scheme Lead to better spatial reuse and higher spectral efficiency. Crosslayer設計與最佳化增進無線傳輸與行動網路的效能。為了設計頻寬上有效的ieee802.16網路，我們偏向使用設計與最佳化在 在application層load需求資訊，實體層interference資訊，以及scheduling與route selection機制在資料連結層。 我們相信干擾在無線環境下是限制網路流量與規模最重要的因素。在資源分配與路徑建立流程時考量干擾的情形影響同步傳輸scheme的設計有較佳的頻寬利用 當限制彼此間干擾。 發展interference-aware Ieee802.16架構具有達成wimax mesh網路整體高利用率。Proposed scheme包含interference-aware route construction 演算法，加強的集中式mesh排程scheme。 2019/4/29 OPLAB,NTUIM

5 Motivation & Problem Overview
Comparison with a/b/g mesh network Advantage from increased range and higher bandwidth. Provide fine granularity radio resource control. TDMA-based scheduling mechanism allows centralized slot allocation. Interference remains a major issue in multi-hop Wimax mesh networks. To Provide high spectral usage, an efficient algorithm for slot allocation is needed, so as to maximized the concurrent transmission of data in the mesh. 相較於IEEE a/b/g網路Wimax mesh網路提供多種優勢如：增加範圍與頻寬。 此種以TDMA的Channel Access的Scheduling在wimax的multihop relay系統提供fine granularity資源控制相較於RTS/CTS based a/b/g系統。 TDMA為基礎的scheuling機制允許centralized的slot allocation，提供整體有效的資源利用。(wimax backhaul mesh網路不同於802.11mesh用於mobile adhoc網路)。 無論如何干擾在multihop wimax網路仍然最主要的問題。為了提供high頻寬使用，一種有效的slot分配演算法是需要的，來最大化資料同步傳輸於網路中。 干擾程度是根據資料如何在網路中被路由。 在文獻中，我們討論下列wimax-based mesh配置情況。網路由單一節點所管理，我們稱作Mesh BS。 作為Mesh網路對於外部網路的界面。我們提供一種interference-aware多點路由選擇對給定的Capacity-Request Matrix來達成有效排程。 2019/4/29 OPLAB,NTUIM

6 Mesh Mode Acronyms 2019/4/29 OPLAB,NTUIM

7 Request and granting procedure
IEEE Mode Operation Entry process MSH-NCFG(Mesh Network Configuration) MSH-NENT(Mesh Network Entry) Request and granting procedure MSH-CSCH(Mesh Centralized Scheduling) MSH-CSCH:Request MSH-CSCH:Grant MSH-CSCF(Mesh Centralized Scheduling Configuration) Mesh BS提供backhaul connectivity與控制SS節點，當使用Centralized排程，BS負責收集capacity需求與管理資源分配。 在wimax mesh中，mesh network configuration(MSH-NCFG)與mesh network entry(MSH-NENT)訊息是用來廣播mesh network 及幫助新節點同步與加入mesh network，適用於fixed wireless backhaul網路。 在mesh中Active節點定期廣播MSH-NCFG訊息和網路描述，其描述基本網路組態資訊如Base ID及被使用的Base Channel。 當新節點想要加入active mesh網路則進行掃描active network並listen MSH-NCFG訊息。 新節點建立coarse同步與開始網路entry process根據MSH-NCFG給予的資訊。 在所有可能的鄰居廣播MSH-NCFG訊息，加入節點(在wimax中稱candidate node)選擇潛在的sponsoring節點來連接。 Mesh Network Entry Message(MSH-NENT)與NetEntryRequest資訊則經由Candidate節點送出要求加入Mesh網路。 Mesh BS協調Radio資源分配在mesh網路中。在Centralized Scheme每個mesh SS估計並傳送其資源Request至Mesh BS. 而Mesh BS決定每個連結的同意資源的數量並連線。而此Request與Granted Process使用Mesh Centralized Scheduling訊息 (MSH-CSCH)類型。SS Capacity Request以MSH:CSCH:Request訊息送出至SS節點的Parent節點。 在Mesh BS決定資源分配後，MSH-CSCH:Grant則從Mesh BS開始沿著路徑傳送回去。為了散佈連結，節點與排程樹組態資訊至 所有mesh網路中的參與者，Mesh Centralized Scheduling Configuration(MSH-CSCF)訊息由BS節點廣播並經由其他中介節點廣播。 2019/4/29 OPLAB,NTUIM

8 Interference-Aware Route Construction Algorithms(1)
To achieve efficient spectral utilization and high throughput in mesh networks, the route construction within the mesh network is crucial. blocking value b(n) number of blocked nodes when node n is transmitting blocking metrics B(k) of a multihop route A given route from the Mesh BS toward an SS node k is introduced to model the interference level of routes in the mesh. Indicates number of blocked nodes by all intermediate nodes along the route from root node toward the destination node k.. 為達成有效頻譜利用與高產出在wimax網路，則路徑建立是關鍵。我們提出一個interference-aware route construction algorithms其考量mesh網路干擾情形。 當節點處於一正在傳輸節點的範圍內則為blocked。而其節點n_i的blocked值b(n_i)為其鄰節點個數。定義block值b(n)其為當n節點在傳輸時的干擾節點數量。 blocking metrics B(k)在路徑上則是指從Mesh中的BS至SS節點k被用來指示在mesh網路中的干擾程度。 multihop路徑的blocking metrics B(k)是從根節點至目的節點k的中介節點的blocked節點的數量。 路徑block metrics為所有沿著路徑傳送或轉送封包的節點block值。則路徑至節點k的blocking metrics則為所有節點b(n_i)(包含來源節點與轉送節點)的總合。 ***在論文中的Interference-aware scheme設計方法是找出一條具有較小干擾的路徑，其中在傳輸範圍中的節點稱作Blocked。 2019/4/29 OPLAB,NTUIM

9 Interference-Aware Route Construction Algorithms(2)
當節點的傳輸干擾目前接收的節點則是被Blocked。 圖二即為blocking metric計算的例子其值大於圖一。 如圖三所示路徑建立演算法，由Mesh BS每次加入一SS節點。而其加入依Time Sequence，並選擇具有最小blocking的Sponsoring節點加入。 在interference-aware路徑建立scheme，Block Metrics資訊存於Network Descriptor在MSH-NCFG訊息。 當新節點尋找active network在加入流程時，根據blocking metrics資訊選擇潛在的sponsoring節點來降低多點傳輸時的干擾與提升效能。 2019/4/29 OPLAB,NTUIM

10 Interference-Aware Route Construction Algorithms(3)
(1) (2) (3) (4) (5) (6) 首先初始化集合S並將父節點向量設成空集合 在鄰節點選出具最高 找出下一個具最高time sequence的節點 交集 選出最小Block metrics加入至父節點向量 (7) 2019/4/29 OPLAB,NTUIM

11 Blocked Node b(1)=2 b(2)=4 b(3)=3 B(1)=4
s s Figure.1 Blocked Node n1 b(1)=2 b(2)=4 d d s s b(3)=3 B(1)=4 如同圖上所示在不同情況下可能節點會干擾距離更遠的節點。其他的blocking metrics的類型，propagation模型與接收者的敏感度) 基於資訊可利用性與系統設計的權衡。 n2 n3 d d 2019/4/29 OPLAB,NTUIM

12 b’(1)=2 b’(2)=4 b’(3)=5 b’(4)=4
s s Figure.2 n1 b’(1)=2 b’(2)=4 d d s s b’(3)=5 b’(4)=4 n2 n3 d d 2019/4/29 OPLAB,NTUIM

13 Interference-Aware Scheduling Algorithms(1)
To exploit concurrent transmission opportunity to achieve high spectral utilization and hence high system throughput. Seeks to maximize the number of concurrent transmissions without creating exceeding interference for other simultaneous transmission. Achieved by taking into the consideration the traffic capacity request of each SS node k from Mesh BS as D(k). Interference-aware的scheduling設計是為運用同步傳輸機會來達成高頻譜利用與高系統效能。 此scheduling尋求同步傳輸最大數目，而不對其他同時傳輸造成額外的干擾。 並經由考量SS節點的traffic capacity request。定義SS節點k的capacity request在BS節點為D(k)。 2019/4/29 OPLAB,NTUIM

14 Interference-Aware Scheduling Algorithms(2)
Mesh BS 同意於radio資源根據App層所有SS節點的capacity request D(k)-s與mesh network的route資訊 我們在entry與初始程序時取得route的資訊，而D(k)可被{等價表達成link demand Y(j) for所有Link}。 Sch演算法遞迴地決定ActiveLink(t)表示時間t時的所有ActiveLink集合。 在Allocation的每一回合，具最高未分配流量需求的link則在下一次的單位流量分配來選擇。 為了滿足同步傳輸SINR限制，blocked_neighbor(k)用來排除鄰近干擾連結。 2019/4/29 OPLAB,NTUIM

15 Interference-Aware Scheduling Algorithms(3)
從時間單位1開始當Link中仍有需求時執行而分配的步驟則在沒有其他未分配流量需求終止。 選出具有最高需求的Link開始進行分配，B為Block節點集合而A為Active Link集合 當Link j中排除Blocking節點並找出下一個需要被分配的Link 將A集合放入ActiveLink中，而進入時間單位下一回合。 2019/4/29 OPLAB,NTUIM

16 Performance Evaluation
Optimal Solution From Linear Program formulated to model the network throughput upper bound of IEEE network. Throughput Performance in Chain Topology Route construction is straightforward. Throughput Performance in Random Topology Locations and a set of mesh nodes are randomly generated. 我們可在兩種情形下評估ieee mesh的系統效能。(1)Linear chain的拓撲(2)Random mesh的拓撲。 並比較於無空間再利用(spatial reuse)的MSH-CSCH排程在ieee802.16a標準的例子，做為本研究基本scheme。 我們研究基於linear規劃下的理論上限。 第一種情況只有考量排程問題在線性chain拓撲ieee802.16mesh網路。在chain拓撲，路徑建立是直接的，例如資料封包是沿著chain來forward。 在第二種情況，我們在random拓撲mesh網路考量排程與路由。一組mesh節點的位置是隨機地產生。 mesh節點加入的順序不與節點的位置相關是隨機決定的。Mesh的形成是由BS節點開始。而後SS節點一個個依序加入。 任何已加入mesh網路的節點可能變成sponsoring節點。當新節點加入現存網路根據在新節點傳輸範圍candidate SN的數量， 可能會聽到多個MSH-NCFG廣播訊息。而在interference-aware routing scheme新節點選擇sponsoring節點做為有最小blocking度量 的candidate SN。相較之下，新節點在random選徑scheme隨機選擇Sponsoring節點。 2019/4/29 OPLAB,NTUIM

17 Optimal Solution From Linear Program
網路活動model interms of介於0至1實數的正規化的時間fraction。 集合S代表所有可能的傳輸schemes interms of 連結頻寬R(bits/sec)。 在給定的傳輸scheme j與acitve傳輸節點t與接收節點r中，S(t,j)是設定成-R(t,r)， 而節點pair(t,r)間的連結頻寬，假設節點t正傳輸至節點r，則S(r,j)設定成+R(t,r)。 所有其他的S(x,j)設定成0，假如節點x即不傳送也不接收在第j個傳輸scheme。 在傳輸scheme中，允許多個並行傳輸，假如所有接收條件滿足。 變數x(j)代表在在單位時間中active的第j個傳輸scheme中的正規化時間fraction。 在所有的接收者，SINR(j)>r是必要的，其為最小reception SINR門檻。 2019/4/29 OPLAB,NTUIM

18 Optimal Solution From Linear Program
2019/4/29 OPLAB,NTUIM

19 Optimal Solution From Linear Program
Since the optimal linear programming algorithm is computed based on arbitrarily slicing of time fractions of all feasible transmission combinations, the performance of the discrete-time event driven design of proposed schemes is capped by the performance of the linear programming algorithm. 此線性規劃演算法的最佳解被用來作為效能比較標桿 for proposed interference-aware mesh scheme。 由於最佳化的線性規劃演算法基於所有可行的傳輸組合的時間fraction的任意分割，proposed scheme的離散時間事件驅動設計的效能被 線性規劃演算法的效能所超過。故線性規劃演算法的效能可當做上限值。 2019/4/29 OPLAB,NTUIM

20 Overall throughput of a chain topology 802.16 network
Figure 6 基本的802.16mesh無interference-aware排程的效能比較proposed scheme與線性規劃的上限，如圖六所示。 我們可看到proposed interference-aware scheme效能接近於上限也顯著的勝過basic ieee802.16mesh。 當在多點802.16網路中節點數量增加時影響並行傳輸的可能性並負面地影響網路效能。 在基本的802.16mesh scheme，由於有限的空間reuse，當節點數量增加時網路的效能顯著的降低。 另一方面，隨著interference-aware並行傳輸，正規化整體效能降低顯著少於節點數量的增加。 Proposed scheme是較basic更加scalable。當relay路徑的長度增加與網路中節點數量時，則整體的網路效能減少由於 幫包需被forward更多次。假設當空間reuse的degree增加少於hop增加的數量則網路效能會降低。 視網路relay hop的數目與網路拓撲，存在可能達成的空間reuse的degree限制。經由比較最佳線性規劃的結果， 我們可知proposed scheme可達到near-optimal網路效能與空間利用。 2019/4/29 OPLAB,NTUIM

21 Throughput Performance of random topology 802.16 mesh
Figure 7 在圖七，我們可知interference-aware與basic排程scheme皆模擬。與chain拓撲相似我們也討論當節點數目增加時造成的整體網路效能減少。 在圖中同時具有interference-aware排徑與選徑演算法的scheme達到最高的效能。而只有interference-aware選徑scheme則具有次佳效能。 而只有interference-aware排程scheme則較basic scheme較佳。最後我們可結論proposed scheme可有效地加強basic scheme mode operation。 在mesh網路排程與選徑建立的設計階段，可以採用interference-aware設計概念，運用較少干擾的同步傳輸的效益。 結果，mesh網路中的spectral utilization是enhanced且有較少干擾與更佳的空間reuse。 2019/4/29 OPLAB,NTUIM

22 A load-aware and interference-aware scheduling algorithm.
Conclusion Allowing concurrent transmissions to achieve high spatial reuse is essential for scalable wireless mesh network. An interference-aware route construction algorithm for mesh network initialization process. A load-aware and interference-aware scheduling algorithm. Effectively improve the network throughput performance in IEEE mesh networks and achieve high spectral utilization. 允許同步傳輸來達成高空間reuse對於scalable mesh網路設計是重要的。 對於實現中的ieee802.16mesh模式來改善spectral utilization。 使用此種架構，運用interference-aware路徑建立演算法於mesh網路初始過程藉由選擇具有最小干擾路徑至現存節點來改善網路效能。 此外，load-aware與interference-aware排程演算法於集中式排程的mesh網路也被討論。 模擬結果顯示proposed scheme有效地改善mesh網路效能與達成較高的spectral利用。 2019/4/29 OPLAB,NTUIM