在無線感測網路中基於不對稱繞送之行動性支援機制

Abstract

本論文針對會動態改變網路拓樸的無線感測網路（Wireless Sensor Network），以感測網路上下傳輸資料量不對稱(一般而言，上傳資料量遠大於下傳資料量)的特性為基礎，提出一套識別碼分配與封包繞送機制以支援感測節點的漫遊與網路繞送路徑的修復。本機制在網路拓樸改變時，不須重新分配識別碼（Identity）即可快速修復無線感測網路的繞送路徑。 在無線感測網路中，感測節點需要識別碼才能識別彼此，也因為如此，感測節點所發出的網路封包才得以正確從傳送端到達目的地。然而無線感測網路的網路拓樸會因為感測節點損壞或移動而改變，此時為了維持感測網路的運作，必須修復網路的繞送路徑，而繞送路徑的修復機制則會因識別碼分配方式而不同。 識別碼的分配方式可分為兩大類:可繞送識別碼分配方式（Routable ID Assignment Mechanism）及不可繞送識別碼分配方式（Non-routable ID Assignment Mechanism）。可繞送識別碼分配方式是指識別碼本身帶有繞送資訊，利用識別碼即可進行封包繞送，不需要利用額外的路由協定產生路由表，例如ZigBee等。因此當網路拓樸改變時，必須重新分配行動感測節點以及其子樹內所有節點的識別碼，否則會無法利用識別碼進行封包的繞送。然而重新分配識別碼不僅需要大量的訊息傳遞，重新分配的時間也可能過長，造成節點間的連線中斷。此類機制的缺點在於識別碼不具移動性（Mobility）及容錯（Fault Tolerance）能力，因此當網路實體會移動或不定期損壞時不適用此類機制。 不可繞送識別碼的分配方式則是利用路由表進行封包繞送，這類方法在網路拓樸改變時，不需重新分配識別碼，但必須更新相關節點上的路由表。更新路由表會產生大量控制訊息，以進行繞送資訊的交換，造成額外負擔，而且更新的時間也可能過長，無法快速、即時的修復繞送路徑。 本論文提出一套識別碼分配與封包繞送的機制，針對無線感測網路中感測節點損壞或移動而產生的繞送問題，提供一套有效率的解決方案。為了避免由於網路節點移動，而造成識別碼重新分配的問題，本機制採用不可繞送識別碼的分配方式，利用一個管理單元集中的分配識別碼。而為了減少因為採用不可繞送識別碼而產生封包繞送的負擔，同時有鑑於感測網路具上下傳輸資料量不對稱的特性，本機制依據深度進行上行封包的繞送，而下行封包則採用來源繞送，因此不需要額外的路由協定來產生路由表，即可繞送封包。 本論文對於所提出的方法，透過目前學術界廣為人知的網路模擬器NS2進行模擬實驗，並以AODV及Zigbee做為比較對象。在實驗中，我們發現由於AODV需要許多廣播的控制訊息，因此無論是交遞的延遲時間，或是交遞所需要的控制訊息量，AODV都明顯比我們的方法多上許多；若以交遞成功的機率來看，Zigbee在多個行動節點同時移動時，由於受限於原本的網路拓樸，不易重新加入網路，容易造成交遞失敗。 本機制可良好地支援行動節點的移動性（Roaming）。同時，在此架構下，由於行動節點可在網路間漫遊而不必重新取得新的識別碼，即可連接上另一個感測網路，進行封包繞送，因此本論文亦可支援各種負載平衡機制，例如以電量或封包流量為考量，調整各個無線網路內行動感測節點的個數。

In this thesis, we proposed an identity assignment and routing mechanism for the wireless sensor networks where the network topology may change dynamically, due to sensor node mobility or failures. With the mechanism, a mobile node needs not acquire a new identity when the mobile node attaches to a new router node or visits a new sensor network, whereas still can receive/deliver packets continuously without interruption. Furthermore, the network needs not perform identity reassignment even when some node nodes are malfunction In wireless sensor networks, sensor nodes have identifies to distinguish each other and routes packets to specific nodes. However, the network topology of sensor nodes may change due to the malfunction or movement of sensor nodes. Each time when the network changes its topology, it needs to re-establish the routing paths among sensor nodes. Nevertheless, mechanisms of recovery routing paths vary with identify assignment schemes. Identity assignment schemes can be classified into two categories: Routable ID Assignment mechanism & Non-routable ID Assignment mechanism. With Routable ID Assignment mechanism, sensor nodes, such as in Zigbee networks, can route packets in accordance of the regulation of identities and need not perform routing algorithm to exchange and maintain routing information. However, when the network topology changes due to sensor node mobility or malfunctions, the identities become inapplicable for packet routing. Therefore, we need to reassign the identities of the mobile or malfunction nodes and all of their descendants to reestablish the routing paths. However, re-assignment of identities may cause a large amount of control messages and long end-to-end delays, and lead to interruption of packet deliveries. With Non-routable ID Assignment scheme, sensor nodes cannot derive routing paths from the identities, and thus need to perform routing algorithm to exchange and maintain routing information for packet delivery. Therefore, no identity re-assignment is needed when the network changes its topology, because sensor nodes establish routing paths by exchanging routing information. However, routing information exchanges may cause a large amount of signal traffic among sensor nodes. Furthermore, the latency of such information exchanges is normally such long that the network cannot recover routing path quickly upon node failures or movements. In this thesis, we propose a novel routing and identity assignment mechanism to support routing path recovery for node failures or movements in wireless sensor networks. In order to eliminate identity re-assignment overhead, we adopt the non-routable identity scheme and assume each node has a unique identity. Moreover, because in wireless sensor networks, downlink traffic is normally much higher than uplink traffic, we propose an asymmetric routing mechanism (ARM) for packet delivery. Furthermore, the proposed mechanism can also facilitate load balancing because nodes can switch points of network attachment very effectively. Finally, we conduct a simulation using a well known network simulator NS2 to compare the performance of ARM with Zigbee and AODV. Experiment results show that ARM can achieve a higher handoff success rate than Zigbee because the preset topology parameters of a Zigbee network restrain the identities that can be used in identity re-assignment. Nevertheless, compared with AODV, ARM incurs much less control messages and has a shorter handover delay because sensor nodes in AODV need to update routing paths upon node failures or movements.