基于Ad Hoc無線傳感網絡的三維智能組網優化算法設計研究

金鑫，婁文忠，王輔輔

(北京理工大學 機電學院，北京100081)

0 引言

Ad Hoc 網絡是一種不需任何固定基礎設施支持便可實現互相通信的分布式自組織網絡［1］，無中心、自組織、多跳路由、具有高度動態拓撲結構。因為具有分布性、動態性、自治性、移動性和異構性等特點，這種不同于蜂窩移動通信網和無線局域網的可自由組網的網絡不僅適用于軍事環境(戰場)和災難救助，在民用環境中(分布式計算和傳感網絡)也得到充分應用［2］。

每一個網絡終端節點都帶有一組無線收發的裝置，使得終端具備路由器和主機兩種功能，能通過自組織形成任意拓撲網絡模型。但是，由于Ad Hoc 使用無線通信技術，具有無線通信系統信道質量低、帶寬有限、節點通信距離有限等特點［3］。Ad Hoc 網絡不能使用傳統網絡的通信方式，所以提出了很多針對性的路由算法。在Ad Hoc 網絡的路由算法中，基于分群的算法是最有效的可伸縮算法。該算法的基本思想是把網絡分為群，每個群有一個群首，群首節點負責群間信息的交換，這樣既保證路由信息的準確性，又可以減少信息數量、提高網絡效率［4］。目前最受關注的Ad Hoc 網絡的路由算法有基于螞蟻算法的分布式路由算法［5］和基于分簇的路由算法［6］。蟻群算法生成的網絡結構中，所有節點地位平等、功能相同、魯棒性較好，通信流量平均地分散到網絡中，但是缺乏可擴展性、路由開銷較大、能量消耗快。分簇算法將網絡中的節點分成不同的簇，并分別對“簇首”和“簇員”節點指定不同的功能:1)減少參與路由計算的節點數量從而有效減少多余的洪泛;2)通過劃分簇，將拓撲變化的影響限制在局部范圍內，減少對路由協議帶來的影響;3)成員節點的功能比較簡單，無須維護復雜的路由信息，這大大減少了網絡中路由控制信息的數量，減少了通信量［7］;4)分簇拓撲結構便于管理，有利于分布式算法的應用，具有較好的可擴展性，適合大規模網絡［8］。

本文選取了分簇算法作為基礎，在原有多種分簇路由算法基礎上，根據實際需要首次提出了一種基于三維空間建立的新型分簇路由算法，優化了生成的拓撲結構，使得網絡具有更好的動態性。

1 分簇路由算法

1.1 分簇路由結構

Ad Hoc 網絡采用分布式控制結構，一般分為平面結構和分級結構。其中平面網絡結構簡單，對于小規模網絡適用，平面網絡拓撲圖如圖1所示。

圖1 平面結構網絡拓撲Fig.1 Planar structure of the network topology

分級網絡采用分簇的方法，將網絡節點分成若干簇群，每個簇群都由一個簇頭和多個簇成員節點構成。簇頭之間可繼續進行分簇，形成更高一級的網絡。簇頭節點可通過預設獲取或通過節點使用算法選舉。簇頭節點主要功能是實現簇結構的穩固、重組和通信，而簇成員只需維護、與簇頭通信即可。

分級網絡又可分為單頻率分級和多頻率分級兩種［9］。如圖2所示，單頻率分級中，所有節點使用同一頻率信號進行通信。為了簇頭之間能正常通信，需要網關節點(同屬兩簇的節點)的支持。簇頭和網關節點形成高一級的網絡，成為虛擬骨干。

圖2 單頻率分級網絡拓撲結構Fig.2 Single frequency hierarchical network topology

如圖3所示，多頻率分級網絡不同網絡級采用不同的頻率進行通信。簇頭節點有兩個頻率，以實現簇群內和簇群間的通信。其中:頻率1 用于簇頭與簇成員之間的通信，頻率2 用于簇頭之間的通信。

1.2 分簇算法描述

定義1 將Ad Hoc 網絡抽象成無向連接圖集G(V，E).其中:V 為網絡中節點的集合;E 為網絡中節點對的通信鏈路的邊集合。eij=vivj(i，j=1，2，…)用來表示圖集中存在一條從vi到vj的路徑，即i 節點和j 節點是一對可互相通信的一跳鄰居節點。

定義2 假定一個集合S?V 由一組網絡節點構成。其中:S 為非空節點集。若v1∈S，?v2∈S 滿足v1和v2能互相通信，那么v1為簇頭，S 為一個簇。若Si∩Sj=?，i≠j，那么簇Si和簇Sj稱為非交疊簇，反之為交疊簇。

圖3 多頻率分級網絡拓撲結構Fig.3 Multi-frequency hierarchical network topology

定義3 對于具有簇頭v1的簇S，如果簇內任意節點v2到簇頭的距離最多為k 跳，那么該簇被稱為k 跳有頭簇［10］。

定義4 一個節點的一跳鄰居節點的個數被稱為該節點的度數dv.

本文的新型算法基于多頻率分級網絡進行設計，不具有網關節點，即建立滿足度數需求的一跳有頭非交疊簇。最終目標是構建一個覆蓋所有網絡節點，計算和通信開銷少，網絡拓撲穩定的分簇網絡。

2 三維智能組網優化算法

2.1 算法設計思想

本文在研究了最小ID 算法、最大節點度算法和塊合并算法3 種典型的分簇算法的基礎上，提出了一種基于三維智能組網的新型分簇算法。

通過檢測計算，選取相鄰節點距離符合傳輸范圍、鄰節點與簇頭節點距離之和大、存活的網絡節點成為該網絡中的簇頭，提高網絡穩定性、減小節點最大負載。該算法具有如下4 個特點:

1)簇頭通過按需自適應進行選舉產生，不是周期性產生。

2)算法的更新是按需的，而不是周期的，降低了網絡維護的開銷。

3)通過限制節點的信號傳輸范圍，減少遠距離節點之間的連接，使得鄰節點與簇頭節點距離小，節省節點能量，延長網絡生存時間。

4)通過給定節點度數的要求選擇適合的簇頭節點，優化簇結構，減少網絡負載，提高信息傳輸效率。

2.2 算法過程描述

應用本算法的網絡節點上裝載有GPS 定位和高度傳感器，以獲得網絡節點相對于地球坐標系的局部三維坐標，執行算法獲得最優簇頭及簇結構。算法過程如下:

1)檢測節點的能量Pvi，若Pvi≠0，節點存活;否則，節點死亡。

2)若節點存活，通過GPS 定位和高度傳感器獲得三維坐標，并對每個節點進行ID 定義.

3)根據普通節點的傳輸范圍，確定能互相進行通信的一跳節點。記錄下一跳網絡節點間的距離，并建立距離表。

4)記錄每個節點vi的所有鄰居節點數，即節點vi的度數，用dvi表示。

5)記錄節點vi和其所有鄰節點，構成節點集N(v).

6)根據距離表計算節點vi到其所有一跳鄰居節點的距離總和

7)計算節點vi的權值

式中:ω1和ω2為不同參數的權重，ω1+ω2=1.

8)根據需求定義最優度數，即最優簇成員數，用σ 表示。

9)選擇具有最大Wvi的節點成為簇頭節點，選擇小于等于σ 個節點作為簇成員。所有已選擇的簇頭節點及簇內成員不再允許進入簇頭選擇。

10)刪除被選取的節點后，重復權值判斷，直至所有節點均成為簇頭或簇成員。

11)判斷簇成員數是否小于最小度數要求，如果不符合，將簇連接到距離近的簇形成新簇。

12)算法結束。

2.3 算法優點

相對于以往的各類分簇算法，該算法具有如下優點:

1)三維網絡算法在二維算法基礎上，增加了高度差，模型更接近真實情況。

2)通過實際檢測定位減少了相對定位的計算，不僅運算量減少，精度也大大增加。

3)通過限制節點的傳輸范圍，減少了遠距離點的連接，刪除了大量鏈路，使得距離表更簡潔，數據量減少。

通過最優度數及最小度數的選取，在滿足實際需求的基礎上，使得簇群數量盡可能少，簡化二級簇頭網絡。

3 仿真分析

根據上述算法，建立如下的模擬環境:實際需求仿真場景區域為700 m ×200 m ×1 m，隨機生成24 個網絡節點分布其中。節點的傳輸半徑選取為為區域寬度。由于節點加入了GPS 定位和高度傳感器，節點能夠獲知其在網絡中的地理位置，網絡拓撲結構容易得到。在模擬中通過傳輸半徑來衡量節點是否能夠進行通信，節點距離如果大于半徑，視為不能通信連接，即在網絡拓撲結構中兩節點不存在連接邊。取權重ω1=0.95，ω2=0.05.

通過數學軟件Matlab 仿真建模，輸出在未建立分簇算法時的三維及二維網絡拓撲結構，以及分簇后的結構;通過對比，對算法進行評估。

3.1 生成網絡

現有的網絡拓撲隨機生成器，很難生成比較理想的網絡拓撲結構，本文通過Matlab 軟件，在隨機拋撒節點的時候使用K 均值聚類算法，使得生成的節點分布和真實情況類似。并根據傳輸半徑要求，形成平面拓撲結構，如圖4所示為三維網絡拓撲結構，如圖5所示為二維網絡拓撲結構。

圖4 三維網絡拓撲結構Fig.4 Three-dimensional network topology

從圖4、圖5可看出，直接生成的網絡拓撲結構復雜，節點間通信較為復雜，時延較高、維護費用高且穩定性不高。

通過新型三維分簇算法優化后，可得到分簇網絡拓撲結構。如圖6所示為三維網絡分簇拓撲結構，如圖7所示為二維網絡分簇拓撲結構。

圖5 二維網絡拓撲結構Fig.5 Two-dimensional network topology

圖6 三維網絡分簇拓撲結構Fig.6 Three-dimensional network clustering topology

圖7 二維網絡分簇拓撲結構Fig.7 Two-dimensional network clustering topology

圖6、圖7中的網絡被分成了4 簇，24 節點屬于孤立簇頭，于是被連接到20，使24 節點成為簇成員，簇4、簇9、簇18、簇20 分別在簇內形成一級網絡，簇頭4、簇9、簇18、簇20 形成二級網絡，兩級網絡信號頻率不同。可發現網絡獲得了極大的優化，拓撲結構變得簡單，節點通信簡化，時延減少，維護費用低，并且網絡穩定。

3.2 簇頭數

簇頭數是評價一個分簇網絡的重要指標，本算法通過控制最優度數，使得簇頭數最小值為4，隨機選取多次仿真數據觀察，發現簇頭數在4 ～5 之間波動，由于規定了最少簇成員數大于等于3，所以使得分簇結果良好，如圖8所示為隨機仿真的簇頭數圖。隨著傳輸半徑的增加，每個節點可與剩余所有點連接，所產生的簇數將恒等于4.

圖8 隨機簇頭數圖Fig.8 The figure of random cluster-head

3.3 分簇平衡度

另一個衡量分簇算法性能的指標就是分簇的平衡度。由于最優度數及最少簇成員數的限制，使得每個簇中的節點大致是等同的，簇的分布均勻、平衡度較好。這里選擇用節點數目的標準差來作為衡量平衡度的標準。通過多次仿真實驗得到平衡度的統計，如圖9所示，標準差基本在0 ～2 之間波動，說明簇的平衡度良好、節點分布均勻。

圖9 平衡度統計圖Fig.9 Statistics figure of balance

4 結論

通過上述仿真可看出，網絡拓撲結構經過新型的三維智能分簇組網算法優化后，遠距離傳輸節點減少，參與路由計算的節點數量減少，網絡復雜度明顯降低，網絡的分簇平衡度良好，分簇均勻，從而節省了節點的能量消耗，使得網絡中節點的存活率延長，降低了網絡重構的概率，同時提高了網絡的抗毀能力。仿真結果驗證了這種新型分簇算法可以較好地應用于Ad Hoc 網絡等具有動態網絡拓撲的網絡中。

本文主要通過理論分析來研究新型的三維智能分簇組網算法，而在實際的工程應用中，限定節點間的傳輸距離、節點間存在障礙物等問題可能會對算法的實現造成一定的影響。在下一步工作中，將通過實物仿真來進行算法進一步的優化設計。

References)

［1］徐佳，李千目，王永利，等. 一種Ad Hoc 網絡動態路徑壓縮技術［J］. 兵工學報，2010，31(6):811 -819.XU Jia，LI Qian-mu，WANG Yong-li，et al. A path compression technique based on dynamic model in Ad Hoc demand routing protocols［J］. Acta Armamentarii，2010，31(6):811 -819.(in Chinese)

［2］陳冬松，劉治國，王光興. 移動Ad Hoc 網絡管理中基于節點定位的簇生成算法［J］.兵工學報，2007，28(10):1200 -1204.CHEN Dong-song，LIU Zhi-guo，WANG Guang-xing. A clustering algorithm based on node location in the mobile Ad Hoc network management［J］. Acta Armamentarii，2007，28(10):1200 -1204.(in Chinese)

［3］金鑫，張堯學，王洪波.一種Ad Hoc 網絡中動態自適應的路由更新算法［J］. 小型微型計算機系統，2005，26(12):2078 -2081.JIN Xin，ZHANG Yao-xue，WANG Hong-bo. Dynamically self-adaptive routing update algorithm for Ad Hoc networks［J］. Mini-Micro Systems，2005，26(12):2078 -2081.(in Chinese)

［4］趙春曉，王光興. 無線網絡中基于最高向量權獨立集的分群算法［J］. 兵工學報，2004，25(5):591 -594.ZHAO Chun-xiao，WANG Guang-xing. A clustering algorithm based on highest vector-weighted independent set in wireless network［J］. Acta Armamentarii，2004，25(5):591 -594. (in Chinese)

［5］Zheng X Q，Guo W，Liu R T. An ant-based distributed routing algorithm for Ad-Hoc networks［C］∥International Conference on Communications，Circuits，and Systems. Chengdu:IEEE，2004:412 -417.

［6］Mario G，Taek J K，Pei G. New cluster formation method for efficient flooding in Ad Hoc networks［C］∥Proceedings of WCNC.Orlando，Florida:WCNC，2002.

［7］沈波，張世永，鐘亦平. 無線傳感器網絡分簇路由協議［J］.軟件學報，2006，17(7):1588 -1600.SHEN Bo，ZHANG Shi-yong，ZHONG Yi-ping. Cluster-based routing protocols for wireless sensor networks［J］. Journal of Software，2006，17(7):1588 -1600.(in Chinese)

［8］徐佳，李陟，李千目，等. Ad Hoc 網絡中一種自適應分簇路由過渡協議［J］.通信學報，2008，29(3):54 -62.XU Jia，LI Zhi，LI Qian-mu，et al. Adaptive clustering routing transition protocol in Ad Hoc networks［J］. Journal of Communications，2008，29(3):54 -62.(in Chinese)

［9］王金龍，王呈貴. Ad Hoc 移動無線網絡［M］.北京:國防工業出版社，2004.WANG Jin-long，WANG Cheng-gui. Ad Hoc mobile wireless networks［M］. Beijing:National Defense Industry Press，2004. (in Chinese)

［10］鄭少仁，王海濤，趙志峰. Ad Hoc 網絡技術［M］. 北京:人民郵電出版社，2005.ZHENG Shao-ren，WANG Hai-tao，ZHAO Zhi-feng. Ad Hoc network technology［M］. Beijing:Posts ＆ Telecom Press，2005.(in Chinese)