金鑫，婁文忠，王輔輔

(北京理工大學(xué) 機(jī)電學(xué)院，北京100081)

0 引言

Ad Hoc 網(wǎng)絡(luò)是一種不需任何固定基礎(chǔ)設(shè)施支持便可實現(xiàn)互相通信的分布式自組織網(wǎng)絡(luò)［1］，無中心、自組織、多跳路由、具有高度動態(tài)拓?fù)浣Y(jié)構(gòu)。因為具有分布性、動態(tài)性、自治性、移動性和異構(gòu)性等特點，這種不同于蜂窩移動通信網(wǎng)和無線局域網(wǎng)的可自由組網(wǎng)的網(wǎng)絡(luò)不僅適用于軍事環(huán)境(戰(zhàn)場)和災(zāi)難救助，在民用環(huán)境中(分布式計算和傳感網(wǎng)絡(luò))也得到充分應(yīng)用［2］。

每一個網(wǎng)絡(luò)終端節(jié)點都帶有一組無線收發(fā)的裝置，使得終端具備路由器和主機(jī)兩種功能，能通過自組織形成任意拓?fù)渚W(wǎng)絡(luò)模型。但是，由于Ad Hoc 使用無線通信技術(shù)，具有無線通信系統(tǒng)信道質(zhì)量低、帶寬有限、節(jié)點通信距離有限等特點［3］。Ad Hoc 網(wǎng)絡(luò)不能使用傳統(tǒng)網(wǎng)絡(luò)的通信方式，所以提出了很多針對性的路由算法。在Ad Hoc 網(wǎng)絡(luò)的路由算法中，基于分群的算法是最有效的可伸縮算法。該算法的基本思想是把網(wǎng)絡(luò)分為群，每個群有一個群首，群首節(jié)點負(fù)責(zé)群間信息的交換，這樣既保證路由信息的準(zhǔn)確性，又可以減少信息數(shù)量、提高網(wǎng)絡(luò)效率［4］。目前最受關(guān)注的Ad Hoc 網(wǎng)絡(luò)的路由算法有基于螞蟻算法的分布式路由算法［5］和基于分簇的路由算法［6］。蟻群算法生成的網(wǎng)絡(luò)結(jié)構(gòu)中，所有節(jié)點地位平等、功能相同、魯棒性較好，通信流量平均地分散到網(wǎng)絡(luò)中，但是缺乏可擴(kuò)展性、路由開銷較大、能量消耗快。分簇算法將網(wǎng)絡(luò)中的節(jié)點分成不同的簇，并分別對“簇首”和“簇員”節(jié)點指定不同的功能:1)減少參與路由計算的節(jié)點數(shù)量從而有效減少多余的洪泛;2)通過劃分簇，將拓?fù)渥兓挠绊懴拗圃诰植糠秶鷥?nèi)，減少對路由協(xié)議帶來的影響;3)成員節(jié)點的功能比較簡單，無須維護(hù)復(fù)雜的路由信息，這大大減少了網(wǎng)絡(luò)中路由控制信息的數(shù)量，減少了通信量［7］;4)分簇拓?fù)浣Y(jié)構(gòu)便于管理，有利于分布式算法的應(yīng)用，具有較好的可擴(kuò)展性，適合大規(guī)模網(wǎng)絡(luò)［8］。

本文選取了分簇算法作為基礎(chǔ)，在原有多種分簇路由算法基礎(chǔ)上，根據(jù)實際需要首次提出了一種基于三維空間建立的新型分簇路由算法，優(yōu)化了生成的拓?fù)浣Y(jié)構(gòu)，使得網(wǎng)絡(luò)具有更好的動態(tài)性。

1 分簇路由算法

1.1 分簇路由結(jié)構(gòu)

Ad Hoc 網(wǎng)絡(luò)采用分布式控制結(jié)構(gòu)，一般分為平面結(jié)構(gòu)和分級結(jié)構(gòu)。其中平面網(wǎng)絡(luò)結(jié)構(gòu)簡單，對于小規(guī)模網(wǎng)絡(luò)適用，平面網(wǎng)絡(luò)拓?fù)鋱D如圖1所示。

圖1 平面結(jié)構(gòu)網(wǎng)絡(luò)拓?fù)銯ig.1 Planar structure of the network topology

分級網(wǎng)絡(luò)采用分簇的方法，將網(wǎng)絡(luò)節(jié)點分成若干簇群，每個簇群都由一個簇頭和多個簇成員節(jié)點構(gòu)成。簇頭之間可繼續(xù)進(jìn)行分簇，形成更高一級的網(wǎng)絡(luò)。簇頭節(jié)點可通過預(yù)設(shè)獲取或通過節(jié)點使用算法選舉。簇頭節(jié)點主要功能是實現(xiàn)簇結(jié)構(gòu)的穩(wěn)固、重組和通信，而簇成員只需維護(hù)、與簇頭通信即可。

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

圖2 單頻率分級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.2 Single frequency hierarchical network topology

如圖3所示，多頻率分級網(wǎng)絡(luò)不同網(wǎng)絡(luò)級采用不同的頻率進(jìn)行通信。簇頭節(jié)點有兩個頻率，以實現(xiàn)簇群內(nèi)和簇群間的通信。其中:頻率1 用于簇頭與簇成員之間的通信，頻率2 用于簇頭之間的通信。

1.2 分簇算法描述

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

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

圖3 多頻率分級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.3 Multi-frequency hierarchical network topology

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

定義4 一個節(jié)點的一跳鄰居節(jié)點的個數(shù)被稱為該節(jié)點的度數(shù)dv.

本文的新型算法基于多頻率分級網(wǎng)絡(luò)進(jìn)行設(shè)計，不具有網(wǎng)關(guān)節(jié)點，即建立滿足度數(shù)需求的一跳有頭非交疊簇。最終目標(biāo)是構(gòu)建一個覆蓋所有網(wǎng)絡(luò)節(jié)點，計算和通信開銷少，網(wǎng)絡(luò)拓?fù)浞€(wěn)定的分簇網(wǎng)絡(luò)。

2 三維智能組網(wǎng)優(yōu)化算法

2.1 算法設(shè)計思想

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

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

1)簇頭通過按需自適應(yīng)進(jìn)行選舉產(chǎn)生，不是周期性產(chǎn)生。

2)算法的更新是按需的，而不是周期的，降低了網(wǎng)絡(luò)維護(hù)的開銷。

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

4)通過給定節(jié)點度數(shù)的要求選擇適合的簇頭節(jié)點，優(yōu)化簇結(jié)構(gòu)，減少網(wǎng)絡(luò)負(fù)載，提高信息傳輸效率。

2.2 算法過程描述

應(yīng)用本算法的網(wǎng)絡(luò)節(jié)點上裝載有GPS 定位和高度傳感器，以獲得網(wǎng)絡(luò)節(jié)點相對于地球坐標(biāo)系的局部三維坐標(biāo)，執(zhí)行算法獲得最優(yōu)簇頭及簇結(jié)構(gòu)。算法過程如下:

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

2)若節(jié)點存活，通過GPS 定位和高度傳感器獲得三維坐標(biāo)，并對每個節(jié)點進(jìn)行ID 定義.

3)根據(jù)普通節(jié)點的傳輸范圍，確定能互相進(jìn)行通信的一跳節(jié)點。記錄下一跳網(wǎng)絡(luò)節(jié)點間的距離，并建立距離表。

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

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

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

7)計算節(jié)點vi的權(quán)值

式中:ω1和ω2為不同參數(shù)的權(quán)重，ω1+ω2=1.

8)根據(jù)需求定義最優(yōu)度數(shù)，即最優(yōu)簇成員數(shù)，用σ 表示。

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

10)刪除被選取的節(jié)點后，重復(fù)權(quán)值判斷，直至所有節(jié)點均成為簇頭或簇成員。

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

12)算法結(jié)束。

2.3 算法優(yōu)點

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

1)三維網(wǎng)絡(luò)算法在二維算法基礎(chǔ)上，增加了高度差，模型更接近真實情況。

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

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

通過最優(yōu)度數(shù)及最小度數(shù)的選取，在滿足實際需求的基礎(chǔ)上，使得簇群數(shù)量盡可能少，簡化二級簇頭網(wǎng)絡(luò)。

3 仿真分析

根據(jù)上述算法，建立如下的模擬環(huán)境:實際需求仿真場景區(qū)域為700 m ×200 m ×1 m，隨機(jī)生成24 個網(wǎng)絡(luò)節(jié)點分布其中。節(jié)點的傳輸半徑選取為為區(qū)域?qū)挾?。由于?jié)點加入了GPS 定位和高度傳感器，節(jié)點能夠獲知其在網(wǎng)絡(luò)中的地理位置，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)容易得到。在模擬中通過傳輸半徑來衡量節(jié)點是否能夠進(jìn)行通信，節(jié)點距離如果大于半徑，視為不能通信連接，即在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中兩節(jié)點不存在連接邊。取權(quán)重ω1=0.95，ω2=0.05.

通過數(shù)學(xué)軟件Matlab 仿真建模，輸出在未建立分簇算法時的三維及二維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以及分簇后的結(jié)構(gòu);通過對比，對算法進(jìn)行評估。

3.1 生成網(wǎng)絡(luò)

現(xiàn)有的網(wǎng)絡(luò)拓?fù)潆S機(jī)生成器，很難生成比較理想的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，本文通過Matlab 軟件，在隨機(jī)拋撒節(jié)點的時候使用K 均值聚類算法，使得生成的節(jié)點分布和真實情況類似。并根據(jù)傳輸半徑要求，形成平面拓?fù)浣Y(jié)構(gòu)，如圖4所示為三維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖5所示為二維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

圖4 三維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.4 Three-dimensional network topology

從圖4、圖5可看出，直接生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，節(jié)點間通信較為復(fù)雜，時延較高、維護(hù)費用高且穩(wěn)定性不高。

通過新型三維分簇算法優(yōu)化后，可得到分簇網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。如圖6所示為三維網(wǎng)絡(luò)分簇拓?fù)浣Y(jié)構(gòu)，如圖7所示為二維網(wǎng)絡(luò)分簇拓?fù)浣Y(jié)構(gòu)。

圖5 二維網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.5 Two-dimensional network topology

圖6 三維網(wǎng)絡(luò)分簇拓?fù)浣Y(jié)構(gòu)Fig.6 Three-dimensional network clustering topology

圖7 二維網(wǎng)絡(luò)分簇拓?fù)浣Y(jié)構(gòu)Fig.7 Two-dimensional network clustering topology

圖6、圖7中的網(wǎng)絡(luò)被分成了4 簇，24 節(jié)點屬于孤立簇頭，于是被連接到20，使24 節(jié)點成為簇成員，簇4、簇9、簇18、簇20 分別在簇內(nèi)形成一級網(wǎng)絡(luò)，簇頭4、簇9、簇18、簇20 形成二級網(wǎng)絡(luò)，兩級網(wǎng)絡(luò)信號頻率不同?？砂l(fā)現(xiàn)網(wǎng)絡(luò)獲得了極大的優(yōu)化，拓?fù)浣Y(jié)構(gòu)變得簡單，節(jié)點通信簡化，時延減少，維護(hù)費用低，并且網(wǎng)絡(luò)穩(wěn)定。

3.2 簇頭數(shù)

簇頭數(shù)是評價一個分簇網(wǎng)絡(luò)的重要指標(biāo)，本算法通過控制最優(yōu)度數(shù)，使得簇頭數(shù)最小值為4，隨機(jī)選取多次仿真數(shù)據(jù)觀察，發(fā)現(xiàn)簇頭數(shù)在4 ～5 之間波動，由于規(guī)定了最少簇成員數(shù)大于等于3，所以使得分簇結(jié)果良好，如圖8所示為隨機(jī)仿真的簇頭數(shù)圖。隨著傳輸半徑的增加，每個節(jié)點可與剩余所有點連接，所產(chǎn)生的簇數(shù)將恒等于4.

圖8 隨機(jī)簇頭數(shù)圖Fig.8 The figure of random cluster-head

3.3 分簇平衡度

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

圖9 平衡度統(tǒng)計圖Fig.9 Statistics figure of balance

4 結(jié)論

通過上述仿真可看出，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)經(jīng)過新型的三維智能分簇組網(wǎng)算法優(yōu)化后，遠(yuǎn)距離傳輸節(jié)點減少，參與路由計算的節(jié)點數(shù)量減少，網(wǎng)絡(luò)復(fù)雜度明顯降低，網(wǎng)絡(luò)的分簇平衡度良好，分簇均勻，從而節(jié)省了節(jié)點的能量消耗，使得網(wǎng)絡(luò)中節(jié)點的存活率延長，降低了網(wǎng)絡(luò)重構(gòu)的概率，同時提高了網(wǎng)絡(luò)的抗毀能力。仿真結(jié)果驗證了這種新型分簇算法可以較好地應(yīng)用于Ad Hoc 網(wǎng)絡(luò)等具有動態(tài)網(wǎng)絡(luò)拓?fù)涞木W(wǎng)絡(luò)中。

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

References)

［1］徐佳，李千目，王永利，等. 一種Ad Hoc 網(wǎng)絡(luò)動態(tài)路徑壓縮技術(shù)［J］. 兵工學(xué)報，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 網(wǎng)絡(luò)管理中基于節(jié)點定位的簇生成算法［J］.兵工學(xué)報，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］金鑫，張堯?qū)W，王洪波.一種Ad Hoc 網(wǎng)絡(luò)中動態(tài)自適應(yīng)的路由更新算法［J］. 小型微型計算機(jī)系統(tǒng)，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］趙春曉，王光興. 無線網(wǎng)絡(luò)中基于最高向量權(quán)獨立集的分群算法［J］. 兵工學(xué)報，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，F(xiàn)lorida:WCNC，2002.

［7］沈波，張世永，鐘亦平. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報，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 網(wǎng)絡(luò)中一種自適應(yīng)分簇路由過渡協(xié)議［J］.通信學(xué)報，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 移動無線網(wǎng)絡(luò)［M］.北京:國防工業(yè)出版社，2004.WANG Jin-long，WANG Cheng-gui. Ad Hoc mobile wireless networks［M］. Beijing:National Defense Industry Press，2004. (in Chinese)

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