支援IEEE 802.11s無線網狀網路無縫交遞之交叉點探索機制

Abstract

本論文針對IEEE 802.11s無線網狀網路（Wireless Mesh Networks），提出一套有效率、支援行動節點（Mobile Nodes）換手到新網狀擷取點（Mesh Access Points）時欲利用交叉點（Crossover Node）的交叉點探索機制。所謂的交叉點即為由對應節點（Corresponding Node，即與行動節點連線的節點）到行動節點連接上的舊擷取點與新擷取點這兩條路徑的交點（Intersection）。行動節點換手時即時找到並利用交叉點對於一些無縫交遞的機制是很重要的。舉凡如Micro-mobility便利用交叉點做為位置更新（Location update）的節點，利用此節點將封包導向（Re-direct）至新擷取點，如此便可以減少位置更新所需花費的時間以及封包繞路的行為；另外，利用交叉點做封包雙向傳送（Bi-casting）即是將封包複製一份分別往新、舊擷取點傳送，如此得以減少封包的遺失率（Loss rates）。 雖然先前已有一些找尋交叉點的方法，但在IEEE 802.11s無線網狀網路環境中，這些方法卻無法正確地運作。在IEEE 802.11s無線網狀網路，網狀擷取點是做為封包路由至行動節點的代理者（Proxy），且是以Layer-2的方式做路由。此路由機制與其他網路環境不同。因為這特色，使得先前找尋交叉點的方法會有下列這些問題：第一，大多數先前研究是針對MN與CN在不同網域下的情形所設計的，因此這些方法當MN與CN在相同網域下時會找到錯誤的交叉點；第二，大多數這些方法是基於以行動節點為導向的路由環境所設計的，即封包的路由是以行動節點為目的進行傳送，並非基於IEEE 802.11s無線網狀網路中以代理為基礎（Proxy-based）的路由環境所設計，因此，即使是MN與CN在同一網域的情形，這些機制也會找到錯誤的交叉點；第三，先前研究皆是針對每一行動節點（Per-station based）的找尋交叉點方式，即每一行動節點連接上擷取點或換手至新擷取點便要重新做找尋交叉點的動作，這樣是很沒有效率的；最後，大多數這些機制皆僅在行動節點連接新擷取點時才做找尋交叉點的動作，如此只適用於利用交叉點做封包導向的情景，並無法運作於欲利用交叉點做封包雙向傳送的動作。因此，本篇論文致力於設計一套有效率的交叉點探索機制，此機制可運作於IEEE 802.11s無線網狀網路找到正確的交叉點且支援不論是封包導向或是封包雙向傳送的換手情形。 本論文提出一適用於IEEE 802.11s無線網狀網路之交叉點探索機制：Per-proxy- Oriented Partition-based（POP）CrN Discovery。IEEE 802.11s無線網狀網路的路由機制使得其交叉點找尋不像其它網路環境那樣容易。如前所述，在IEEE 802.11s無線網狀網路，網狀擷取點是做為封包傳送至行動節點的代理者（Proxy）。對應節點所連接上的網狀擷取點，或稱為來源網狀擷取點（source MAP）與舊網狀擷取點以及新網狀擷取點便可決定一交叉點，並且，相同的舊網狀擷取點以及新網狀擷取點其交叉點會隨來源網狀擷取點的不同而不同。此外，真實IEEE 802.11s無線網狀網路佈建上，其路由路徑是幾乎不變的。 POP機制有以下三個特點：針對每個網狀擷取點（Per-proxy-oriented）之交叉點找尋，每個網狀擷取點一次性（One-time）分群（Partition-based）之交叉點找尋以及交叉點資訊分散式化。所謂的每個網狀擷取點之交叉點找尋即POP是針對每個來源網狀擷取點做交叉點找尋程序，如此對於MN與CN不論在不同網域或是同一網域的連線情形都可以找到正確的交叉點；此外，POP僅針對每個網狀擷取點利用分群的概念做一次性的交叉點找尋動作，並且其交叉點資訊是分散儲存在交叉點上，此項特點除了可以縮短交叉點找尋的程序外，還可以減少找尋交叉點程序所需花費的訊息量；最後，交叉點資訊分散式化使得此機制可以很彈性的運作於任何無接縫換手時欲利用交叉點的情景，亦即封包導向或是封包封包雙向傳送都可以利用POP機制正確且快速地找到交叉點。 為了驗證POP機制其效能並與其它交叉點找尋機制做比較，我們使用了學術界廣為人知的網路模擬器NS2進行模擬實驗並與Cross Router Pre-Discovery（CRPD）做比較。這是由於CRPD也是由來源節點（此為GW）去做找尋交叉點的動作，雖然並不是由來源代理者。實驗結果顯示POP在交叉點找尋所需花費的訊息量會較CRPD來的少，這是因為POP所花費的訊息量並不受行動節點的數量與其換手次數的影響。

In this thesis, we proposed an effective Crossover Node (CrN) discovery mechanism for Mobile Nodes (MN), which may change their attached Mesh Access Points (MAPs), in IEEE 802.11s Wireless Mesh Networks (WMNs). A CrN for an MN is the intersection of the path from a corresponding node (CN), which is communicating with the MN, to the MN’s old Access Point (oAP) and the one from the CN to the MN’s new AP (nAP). Finding CrNs for an imminent handover is crucial to some seamless handover schemes. Micro-mobility schemes employ CrNs to localize location updates and re-direct data packets coming from CNs to nAP, and thus can reduce both the latencies of location updates and packet deliveries during handovers. Bi-casting utilizes for generating two duplicated data stream to both oAP and nAP, to reduce packet loss rates during handovers. Although some CrN discovery methods have been proposed previously in the literature, none of them can work correctly, not to say efficiently, for 802.11 WMNs. In 802.11s WMNs, MAPs serve as proxies that perform layer-2 routing to deliver packets on behalf of stations. The proxy-based layer-2 routing mechanism make 802.11s WMNs different than other wireless networks. As a consequence, all previous CrN discovery methods possess some of the following four problems. First, most of the previous Crossover Node discovery mechanisms are designed for an MN’s inter-domain sessions with external CNs that situated at domains differ than the one visited by the MN, thus may find incorrect CrNs for the MN’s intra-domain sessions with internal CNs. Second, most of them are station-oriented and intended for the station-to-station routing, not for the proxy based one as in 802.11s WMNs. Therefore, some of the previous mechanism may find incorrect Crossover Node even for the MN’s inter-domain sessions. Third, all previous mechanisms are per-station based approaches and need to perform a CrN discovery procedure for an MN’s each communication session with a CN, each time when the MN moves. Therefore, they all cannot work efficiently for 802.11s WMNs. Last but not least, most of previous schemes perform CrN discovery procedure only when MNs attach to nAPs and thus can only use CrN for data re-direction not for bi-casting. Therefore, this thesis aims for designing an effective CrN discovery mechanism that can find the correct CrN for 802.11s WMNs and support both data re-direction and bi-casting. In this thesis, we propose a Per-proxy-Oriented Partition-based (POP) CrN Discovery Scheme for 802.11s WMNs. The characteristics of 802.11s WMNs make CrN discovery in 802.11s WMNs different from that in other wireless networks. In 802.11s WMNs, MAPs serve as proxies for routing packets on behalf of stations. Therefore, the serving MAP of a CN, henceforth called source MAP (sMAP), and the old MAP (oMAP) and new MAP (nMAP) of an MN determine a unique CrN for the communication path from the CN to the MN, and different sMAP may result in different CrN for a pair of oMAP and nMAP. Furthermore, in a real deployment of 802.11s WMNs, the route between two MAPs are likely to be static. Therefore, POP adopts three design principles, Per-proxy-oriented CrN discovery, One-time Partition-based approach, and Distributed CrN tables. By adopting Per-proxy-oriented CrN discovery, POP performs a CrN discovery process for each sMAP and thus can find the correct CrN for all sessions, not matter inter- or intra-domain, of an MN. Furthermore, POP performs the CrN discovery procedure just once for each sMAP by using the concept of set partitioning and storing the CrN information at each CrN itself. The One-time Partition-based approach and Distributed CrN Tables, together, not only speedup the CrN discover processes but also reduce significantly the number of messages required for the processes. Finally, Distributed CrN Tables also make it very flexible in using CrN for seamless handover techniques; POP can be used for both data re-direction and bi-casting. In addition of comparing POP qualitatively with other CrN discovery schemes, we also conduct a simulation using a well known network simulator NS2 and compare POP qualitatively with Cross Router Discovery (CRPD) scheme because it also performs CrN discovery from source node, although not the source proxy. Experiment results show that POP outperforms CRPD in terms of the number of discovery messages because the number of discovery messages introduced by POP is independent of the number of MNs in a 802.11s WMN and the number of handovers each MN encountered.