無線自組網絡中的基于多個支配集的路由協議

摘要：提出了一種在無線自組網絡中建立多個連通支配集，使其分時共同承擔網絡中繼傳輸的方法，以防止部分節點被過度消耗，維持網絡中能量消耗的平衡。仿真實驗表明，基于多個連通支配集的路由方法可有效防止部分節點被過度消耗、維護網絡的能量消耗平衡、延長網絡的壽命。

關鍵詞：計算機網絡；無線自組網絡；連通支配集；路由協議

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)05－0280－03

Ad hoc網絡是一處無基礎設施的無線移動網絡，采用電池組供電。能量維持時間過短是Ad hoc網絡發展的主要瓶頸之一[1]。能耗控制的路由協議是延長網絡維持時間的重要途徑之一。文獻[2]中描述了基于連通支配集的路由協議，在網絡中建立連通支配集，通過支配集進行中繼傳輸，使得網絡的路徑搜索空間降至連通支配集的規模，以降低路徑的計算復雜度并減少大量的冗余數據，從而減少了網絡總能量的消耗。在基于連通支配集的路由協議中，連通支配集內的節點往往需要承擔過多的數據通信，易被過度消耗而失效，因此存在嚴重的能量消耗不平衡問題。

在基于連通支配集的路由協議基礎上，本文提出了基于多個連通支配集的路由方法。在網絡中建立多個連通支配集，通過多個連通支配集輪流工作，共同分時承擔網絡的數據傳輸，有效地維持了網絡能量消耗的平衡，從而延長了網絡的壽命。

1基于連通支配集的路由協議

通常認為，降低Ad hoc網絡的能耗需要從網絡的物理層、數據鏈路層、網絡層（路由協議所在層）上進行相應的改進，能耗控制的路由協議屬于網絡層的范疇。

基于連通支配集的路由協議（Dominating－set－based Routing)的目的是在網絡建立基本的連通支配集（Dominating Set），通過連通支配集進行數據傳輸，降低網絡路徑的搜索空間和網絡邏輯結構的復雜度，從而降低網絡通信過程的能量消耗。

該協議建立在圖論的連通支配集概念之上，通常用圖G=（V，E）表示Ad hoc網絡的拓撲結構。其中，V表示Ad hoc網絡的節點集，每個節點表示網絡中一個移動的帶有無線接入裝置的主機；E表示邊集，若節點u、v間存在邊e=(u，v)，則說明節點u與v可以直接連通，即u與v彼此在對方的發射半徑之內。在Ad hoc網絡中，所有節點被看成是對等的，即若u在v的發射半徑之內則v也在u的發射半徑之內。因此圖G為無向圖。在網絡圖G中，若存在子圖g使得網絡中的所有節點或屬于g，或是g中某一節點的鄰居，則稱g為網絡G的支配集；若g為連通的，則稱g為連通支配集（Connected Dominating Set）；若g為節點數目最少的連通支配集，則稱g為最小連通支配集。支配集中的節點成為網關節點（Gateway Node），支配集外的節點成為非網關節點（Non－gateway Node）。圖1表示某簡單的Ad hoc網絡。其中{v，w}構成了網絡的一個最小連通支配集，v、w為網關節點。

在基于連通支配集的路由協議中，只有支配集中的節點（網關節點）才需要作為中繼節點進行數據傳輸，而支配集之外的節點無須進行中繼傳輸。網絡中的節點若要發送數據至目標節點，首先將數據發送至最近的網關節點，在連通支配集中選擇路徑，經過多級中繼傳輸將數據發送至目標節點。如圖1中節點u需要發送數據至節點y，首先將數據發送至相鄰的網關節點v；由此數據傳輸至支配集中，在支配集中選擇最優的路徑傳輸至目標節點。其過程為u→v→w→y。

通過建立連通支配集，使得網絡的路徑搜索空間降至連通支配集的規模，從而降低路徑的計算復雜度，避免發送大量的冗余數據。能否快速建立連通支配集以及所得連通支配集的精簡度是決定基于連通支配集的路由協議效率的關鍵因素。

然而在網絡中構造精確的最小連通支配集是一個NP完全問題，所以通常需要構造近似的最小連通支配集。文獻[3]提出了一種能夠快速建立近似的最小連通支配集的算法。MIT的一個研究組在文獻[4]中對標定網關節點的過程進行了改進，使構造的連通支配集更加精簡。在文獻[5]中對連通支配集進行局部化，可進一步提高維持網絡路由信息的效率。文獻[6]中提出了一種連通支配集精簡算法，對已知的連通支配集進行精簡；鐘曉峰等人[7]提出了一種數據傳輸的全網同步算法，可降低網絡數據傳輸的消耗。

但是基于連通支配集的路由協議中，連通支配集內的節點往往因為承擔過多的數據通信任務而過度消耗，過早因能量耗盡而失效。在圖1所示的網絡中，當u、x、v、z等非網關節點各自發送一次數據時，網關節點v、w總共需要進行四次數據發送，且網關節點發送數據的頻率隨著網絡規模增長而增長。支配集中節點被過度消耗、網絡能耗不平衡是基于連通支配集的路由協議的嚴重缺陷。

2建立多個連通支配集的過程

3基于多個連通支配集的路由協議

基于多個連通支配集的路由協議建立在基于連通支配集的路由協議基礎上。其基本過程如下：

(1)建立多個不相交的連通支配集；

(2)選擇其中一個連通支配集，將該支配集作為當前工作的路由框架，按照基于連通支

配集的路由協議進行通信；

(3)經過一個周期后，將當前連通支配集轉入休眠狀態，將下一個連通支配集作為工作連通支配集，進行基于新的連通支配集的通信。

決定基于多個連通支配集的路由協議效率的關鍵是能否在Ad hoc網絡中快速建立多個不相交的連通支配集。當網絡中存在多個不相交的連通支配集時即可進行基于多個連通支配集的路由協議的通信。當網絡中存在多個連通支配集，但連通支配集有交集時需要對其進行進一步的討論。當各連通支配集的共同節點數所占支配集中節點數比例較小時，基于多個連通支配集的路由協議仍然可對部分節點的能量消耗起到平衡作用。

4仿真實驗及其分析

假設有網絡如圖4所示。網絡中各節點無區別，電池組維持時間一定。以下在相同網絡和相同初始條件下，分別對基于連通支配集的路由協議和基于多個連通支配集的路由協議進行仿真，并對所得數據進行分析比較。

此仿真實驗分別對基于連通支配集的路由協議和基于多個連通支配集的路由協議兩種方法進行仿真。兩次實驗中，網絡進行了相同時間和相同量的數據發送。通過對網絡中的節點能量進行監視，得出各時刻節點能量數值。圖6和7繪出了實驗1和2中連通支配集的能量隨時間變化的曲線。

5結束語

在Ad hoc網絡中，基于連通支配集的路由協議可減少網絡通信過程中能量消耗的總量，而不能維持網絡中節點能量消耗的平衡。網絡中連通支配集中的節點由于要承擔較多的通信任務而被過度消耗，本文采用多個連通支配集的路由方案引入了對連通支配集進行輪換的機制，使其共同分時承擔網絡的數據中繼傳輸，從而找到了避免部分節點被過度消耗的途徑。基于多個連通支配集的路由方法相對基于連通支配集的路由協議更能維持網絡能量的平衡。

參考文獻：

［1］ FEENEY L，NILSSON M.Investigating the energy consumption of a wireless network interface in an Ad hoc networking environment：IEEE Conference on Computer Communications[C].Anchorage:IEEE Press，2001:1548－1557.

［2］WU Jie， LI Hailan.A dominating－set based routing scheme in Ad hoc wireless networks[J].Special Issue on Wireless Networks in the Telecommunication Systems Journal，2001，18(1－3):13－36.

［3］WU Jie，WU Bing，STOJMENOVIC I.Power－aware broadcasting and activity scheduling in Ad hoc wireless networks using connected dominating Sets[J].Wireless Communications and Mobile Computing，2003，3(4):425－438.

［4］WU Jie.Extended Dominating－set－based routing in Ad hoc wireless networks with unidirectional links[J].IEEE Transactions on Parallel and Distributed Computing， 2002，9(3):189－200.

［5］CHEN Benjie，JAMIESON K，BALAKRISHNAN H.Span:an energy－efficient coordination algorithm for topology maintenance in Ad hoc wireless networks[J].ACM Wireless Networks Journal，2002，8(5):481－494.

［6］DAI Fei，WU Jie.An extended localized algorithm for connected dominating set formation in Ad hoc wireless networks[J].IEEE Transactions on Parallel and Distributed Systems， 2004，15(10):908－920.

［7］鐘曉峰，王有政，梅順良，等.基于時分系統的無線自組織網絡同步算法[J].清華大學學報：自然科學版，2005，45(1)：1－45.



注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”