基于二跳信息的分簇算法

摘 要：對于低功耗自組織的無線傳感器網(wǎng)絡，其路由協(xié)議和拓撲控制受到了很多學者的關注，且已成為國際的研究熱點。在分析了LEACH，F(xiàn)SR算法的基礎上，提出了一種基于二跳信息的分簇算法，以有效提高網(wǎng)絡生命期。著重對算法的設計思想和工作過程，包括簇首選擇與簇建立，簇成員通信等進行了分析和論述。仿真結果表明本文中的算法對于LEALCH能有效提高網(wǎng)絡生命期。



關鍵詞：分簇算法；無線傳感器網(wǎng)絡；二跳；多跳；系統(tǒng)壽命；生成樹

中圖分類號：TN915 文獻標識碼：B

文章編號：1004373X(2008)0100703

A Cluster Based on Binary[CD*2]hop Algorithm



FANG Junrong，LIU Sanyang

(College of Science，Xidian University，Xi′an，710071，China)



Abstract：The router protocol and topologic control of the wireless sensor network，which has the properties of self[CD*2]organized and lower power，are concerned by many scholars.The study on them has become international popular.Based on the analysis of LEACH algorithm and FSR algorithm，we propose a clustering algorithm based on binary[CD*2]hop information.The proposed algorithm can improve the life time of the network effectively.We mainly make an analysis and description of the design idea and the working process of the proposed algorithm，including the first choice and the building of the clusters and the communication among the clusters.The simulated result shows the efficience of the proposed algorithm on improving the life time of the network.



Keywords：clustering algorithm；WSN；binary[CD*2]hop；multi[CD*2]hop；system life；spanning tree

1 引 言

無線傳感器網(wǎng)絡是由一組稠密布置、隨機撒布的傳感器構成的無線自組織網(wǎng)絡，其目的是協(xié)作地感知、采集和處理網(wǎng)絡覆蓋的地理區(qū)域內(nèi)感知對象的信息，并發(fā)布給觀察者。由于無線傳感器網(wǎng)絡具有低成本、自組織、體積小和布撒靈活等特性，因此在軍事、環(huán)境科學、醫(yī)療健康、空間探索、工業(yè)傳感、安全監(jiān)控和交通控制等領域有著廣闊的應用前景。

對于無線傳感器網(wǎng)絡研究，目前主要集中在硬件平臺、體系結構、網(wǎng)絡協(xié)議和數(shù)據(jù)管理，以及與應用相關的共性技術(如時間同步、定位機制等)上。網(wǎng)絡協(xié)議與拓撲控制，特別是以基于簇的路由協(xié)議為代表的網(wǎng)絡層協(xié)議，是國際上研究的重點和熱點之一。

本文主要對簇組織問題進行研究，在借鑒國際同類研究成果的基礎上，我們提出了一種基于二跳信息的分簇算法。其特點如下：

采用局部算法動態(tài)選擇簇首，適時輪換；

具備簇自愈能力；

貫穿能量控制過程；

簇成員同簇首之間多跳通信。

2 研究基礎

目前在國際上有代表性的基于簇的無線傳感器網(wǎng)絡路由算法主要包括LEACH(Low[CD*2]Energy Adaptive Clustering Hierarchy)和TEEN(Threshold sensitive Energy Efficient sensor Network protocol)等。文獻\\[1\\]介紹了LEACH算法，他突破了平面網(wǎng)絡的思想，采用分層、分簇的方法解決了很多在平面層經(jīng)常會遇到的問題，并有效地提高了網(wǎng)絡壽命期。文獻\\[2\\]和文獻\\[3\\]提出了FSR算法，即根據(jù)魚眼技術的思想提出的算法，他通過局部算法能有效提高精度。

借鑒上述研究的經(jīng)驗，為了使問題域更加集中且不失一般性，我們在算法設計時假設:

(1) 任意兩節(jié)點間的通信鏈接具有雙向性；

(2) 所有節(jié)點具有相同的最大發(fā)射功率Pmax，覆蓋半徑rmax；

(3) 忽略外因，確保節(jié)點發(fā)射功率與通信距離成同向變動關系。

3 算法設計

3.1 LEACH算法

LEACH(Low Energy Adaptive Clustering Hierarchy)是MIT的Chandrakasan等人為無線傳感器網(wǎng)絡設計的低功耗自適應聚類路由算法。與一般的平面多跳路由協(xié)議和靜態(tài)聚類算法相比，LEACH可以將網(wǎng)絡生命周期延長15%，主要通過隨機選擇聚類首領平均分擔中繼通信業(yè)務來實現(xiàn)。在LEACH中，一輪由初始化和穩(wěn)定工作兩個階段組成，為了避免額外的處理開銷，穩(wěn)定態(tài)一般持續(xù)相對較長的時間。在初始化階段，傳感器節(jié)點生成0，1之間的隨機數(shù)，如果大于閥值T，則選該節(jié)點為聚類首領。T的計算方法如下：T=p1－p\\[r mod(1/p)\\]，其中p為節(jié)點中成為聚類首領的百分數(shù)，r是當前的輪數(shù)。一旦聚類首領被選定，他們便主動向所有節(jié)點廣播這一消息。依據(jù)接收信號的強度，節(jié)點選擇他所要加入的組，并告知相應的聚類首領。基于時分復用的方式，聚類首領為其中的每個成員分配通信時隙。在穩(wěn)定工作階段，節(jié)點持續(xù)采集檢測數(shù)據(jù)，傳于聚類首領，進行必要的融合處理之后，發(fā)送到sink節(jié)點，這是一種減小通信業(yè)務量的合理工作模式，持續(xù)一段時間以后，整個網(wǎng)絡進入下一輪工作周期，重新選擇聚類首領。

3.2FSR算法

FSR(Fisheye State Routing，魚眼路由) 協(xié)議是為實現(xiàn)Ad hoc網(wǎng)絡路由而提出來的。FSR是一個先驗式的路由協(xié)議，他使用了魚眼技術，在不同魚眼域中的節(jié)點以不同的頻率向鄰居節(jié)點廣播鏈路更新信息，這能夠大大減少鏈路狀態(tài)更新信息，從而降低了泛洪的開銷。通過節(jié)點之間相互交換鏈路狀態(tài)消息，每個FSR路由器都能獲知網(wǎng)絡全局的拓撲信息，根據(jù)這些最新的拓撲信息，F(xiàn)SR為每個目的節(jié)點計算最短路徑。由于鏈路更新頻率由距離決定，因此對于域內(nèi)的節(jié)點路由都是精確的，而對于域外的節(jié)點，離目的節(jié)點越遠，路由的精確度便越低，這是因為距離較近的更新較快，較遠的更新較慢，但不會像按需路由那樣需要花時間去尋找路由，因此能維持較低的延時，而且隨著離目的節(jié)點越來越近，路由信息越來越精確，正好彌補了路由的不精確性。在移動網(wǎng)絡中，逐漸精確的路由減小了節(jié)點移動對路由精確度的影響，目的序列號的使用不僅使得FSR能使用最新的鏈路狀態(tài)信息去維護拓撲結構，而且還避免了環(huán)形路由的形成，因此較適合高移動性的無線網(wǎng)絡。

3.3 本文算法描述

通過對LEACH和FSR的算法分析，我們利用LEACH的分簇思想和FSR的多跳思想設計了本文的算法。其基本思路是先預選一些簇頭(按照剩余能量的多少來判斷哪些節(jié)點被優(yōu)先選取，還要分布比較均勻)，以簇頭為中心，其一跳、二跳鄰節(jié)點為其簇成員，若存在其一跳或二跳鄰節(jié)點為簇頭，則其中剩余能量較少的被取消簇頭資格，也就是說兩簇頭之間必須三跳或三跳以上距離。以這些預選簇頭進行分簇，若分簇完后還有一些節(jié)點沒有被覆蓋，則在這些未被覆蓋的節(jié)點中選取一節(jié)點為簇頭，進行分簇，直到所有節(jié)點被覆蓋為止。為此，我們?yōu)檎麄€網(wǎng)絡進行了基于二跳信息的分簇，總體來說簇頭分布比較均勻、合理，而且在其中也考慮了負載平衡的因素。

下面對簇間進行簡單的分析。

由上面的簇形成過程可知，簇頭與簇頭之間的通信距離只可能是三跳，四跳或五跳，或者是簇與簇之間不連通。

(1) 當簇頭與簇頭之間的通信距離為三跳時，如圖1所示。

V1為CH1的一跳節(jié)點，V3為CH2的一跳節(jié)點，V2同為CH1和CH2的二跳節(jié)點，則在進行分簇時，V2為剩余能量較多的簇頭的簇成員或者離的較近的那個簇頭的簇成員。在圖2中V2離CH2較近，所以為CH2的簇成員。

(3) 當簇頭與簇頭之間的通信距離為五跳時，分簇如圖3所示，V1，V2為CH1的簇成員，V3，V4為CH2的簇成員。

以下是對簇內(nèi)的分析:

若一簇如圖4所示，其中簇頭為節(jié)點CH，其一跳鄰居節(jié)點在他的覆蓋范圍以內(nèi)，其二跳節(jié)點為簇頭CH的一跳鄰居節(jié)點的鄰居節(jié)點，顯然他們在簇頭CH的以其兩倍覆蓋半徑的圓內(nèi)。由圖4所示，并非所有在以簇頭CH兩倍覆蓋半徑的圓內(nèi)的節(jié)點都為簇頭CH的二跳節(jié)點，其中V1，V3，V4，V5為簇頭CH的三跳節(jié)點，V2，V6為簇頭CH的四跳節(jié)點。

為不失一般性，我們假設網(wǎng)絡中的節(jié)點都是連通的。如圖4，一簇為以節(jié)點CH為簇頭，其一跳鄰居節(jié)點和二跳節(jié)點為簇成員。構造無向圖G=(V，E)，其中V為簇內(nèi)節(jié)點的集合，E為簇內(nèi)節(jié)點間的邊，若兩節(jié)點間的距離大于他們的覆蓋半徑，則這兩節(jié)點不能直接通信，即這兩節(jié)點間沒有邊。我們對簇內(nèi)節(jié)點構造最小生成樹，這樣可以節(jié)省簇內(nèi)總體能量的消耗，延長網(wǎng)絡生命期，并能有效控制個別節(jié)點的過度消耗而導致過早死亡。

假定無向圖中邊上的權值為兩節(jié)點間的通信代價，對于構造最小生成樹，我們采用Dijkstra算法。如圖5所示，一隨機產(chǎn)生的20個節(jié)點的網(wǎng)絡，利用Dijkstra算法得到的最小樹為紅線表示的路徑。

3.4 算法性能分析

算法的性能包括算法的復雜度和算法結果兩方面。由于本文中的算法是個分布式算法，算法的復雜度包括時間復雜度和消息復雜度。算法中兩個重要的因素是節(jié)點覆蓋半徑和初始簇頭節(jié)點的預選。節(jié)點覆蓋半徑是硬件相關的，需要根據(jù)傳感器節(jié)點的功率和傳感器的物理拓撲來確定；初始簇頭節(jié)點應盡量做到均勻分布于整個區(qū)域中。在上面兩個關鍵因素合理的情況下，初始的分簇比較合理；分簇算法的調(diào)整會消除冗余的簇，同時增加簇間的負載平衡度和減少簇平均能耗。

4 仿真與比較

不失一般性，我們考慮了一個方形區(qū)域，傳感器節(jié)點隨機分布在此區(qū)域中，取100個傳感器，5~7個傳感器被預選為簇頭進行實驗。模擬網(wǎng)絡的拓撲為區(qū)域長為50，寬為50，傳感器的覆蓋半徑為12，基站在坐標點(0，-100)處，能量模型采用文獻\\[1\\]中的，假設每個傳感器的初始能量為2 J，數(shù)據(jù)包為10 kb，發(fā)射和接收的能量消耗為50 nJ/b，傳輸放大系數(shù)為100 pJ/b/m2。利用Matlab仿真算法如下：

本文算法與LEACH算法的仿真結果如圖6所示。我們假設網(wǎng)絡的生命期為第一個傳感器失效的時間，則由圖6可知，本文算法比LEACH算法有效提高了網(wǎng)絡生命期，并且對于整個網(wǎng)絡，利用LEACH算法傳感器失效更快。由于本文算法在設計時考慮了分簇均勻，能量負載均衡，且簇內(nèi)算法高效，所以利用本文算法能延長網(wǎng)絡生命期，傳輸更多的有效數(shù)據(jù)。

5 結 語

分簇算法用來把整個傳感器網(wǎng)絡劃分為負載平衡性較好、平均能耗較小的簇，用于網(wǎng)絡初始自組織階段。由于算法是分布式的，在分簇后就可以使用簇內(nèi)簇頭選舉和簇內(nèi)、簇間路由算法。本文中提出的分簇算法以延長整個無線傳感器網(wǎng)絡的生命期為目的，具體分析時考慮了簇合理性、平均能耗和負載平衡性。下一步的工作將對簇內(nèi)算法以及簇頭與簇頭之間做進一步的研究，在簇內(nèi)構造度約束最小生成樹，以進一步減少整個網(wǎng)絡的總體能耗，以達到延長網(wǎng)絡生命期的目的。

參 考 文 獻

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].In Proceeding of the 33rd Hawai International Conference on System Sciences，2000.

［2］Pei G，Gerla M，Chen T W.Fisheye state routing:a routing scheme for ad hoc wireless networks[C].Proceedings，IEEE International Conference on Communications，2000:70-74.

［3］Yang Chunchuan，Tseng Lipin.Fisheye Zone Routing Protocol for Mobile Ad Hoc Networks.IEEE，2004.

［4］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡\\[M\\].北京:清華大學出版社，2005.

［5］[德]Holger Karl，Andreus Willig.無線傳感器網(wǎng)絡協(xié)議與體系結構[M].邱天爽，唐洪，李婷，等譯.北京:電子工業(yè)出版社，2007.

［6］任豐原，林闖.無線傳感器網(wǎng)絡[J].軟件學報，2003，14(2):1 148-1 157.

［7］Zhao Baohua，Zhang Wei.Cluster Partition Algorithm in Wireless Sensor Networks[J].Chinese Journal of Computers，2006，29(1).

［8］Cao Yongtao，He Chen.A Distributed Backoff[CD*2]based Clustering Algorithm for Wireless Sensor Networks[J].Journal of Shanghaijiaotong University，2006，40(7).

［9］Liu Linfeng，Liu Ye.Topology Control Scheme Based on Simulated Annealing Algorithm in Wireless Sensor Networks[J].Journal on Communication，2006，27(9).



作者簡介 方軍榮 男，1981年出生，碩士研究生。主要研究方向為最優(yōu)化理論與算法，無線傳感器網(wǎng)絡。

劉三陽 男，1959年出生，教授，博士生導師。主要研究方向為現(xiàn)代優(yōu)化理論與方法，網(wǎng)絡算法及其應用等。

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