摘 要：對(duì)于低功耗自組織的無線傳感器網(wǎng)絡(luò)，其路由協(xié)議和拓?fù)淇刂剖艿搅撕芏鄬W(xué)者的關(guān)注，且已成為國際的研究熱點(diǎn)。在分析了LEACH，F(xiàn)SR算法的基礎(chǔ)上，提出了一種基于二跳信息的分簇算法，以有效提高網(wǎng)絡(luò)生命期。著重對(duì)算法的設(shè)計(jì)思想和工作過程，包括簇首選擇與簇建立，簇成員通信等進(jìn)行了分析和論述。仿真結(jié)果表明本文中的算法對(duì)于LEALCH能有效提高網(wǎng)絡(luò)生命期。



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

中圖分類號(hào)：TN915 文獻(xiàn)標(biāo)識(shí)碼：B

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

對(duì)于無線傳感器網(wǎng)絡(luò)研究，目前主要集中在硬件平臺(tái)、體系結(jié)構(gòu)、網(wǎng)絡(luò)協(xié)議和數(shù)據(jù)管理，以及與應(yīng)用相關(guān)的共性技術(shù)(如時(shí)間同步、定位機(jī)制等)上。網(wǎng)絡(luò)協(xié)議與拓?fù)淇刂?，特別是以基于簇的路由協(xié)議為代表的網(wǎng)絡(luò)層協(xié)議，是國際上研究的重點(diǎn)和熱點(diǎn)之一。

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

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

具備簇自愈能力；

貫穿能量控制過程；

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

2 研究基礎(chǔ)

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

借鑒上述研究的經(jīng)驗(yàn)，為了使問題域更加集中且不失一般性，我們?cè)谒惴ㄔO(shè)計(jì)時(shí)假設(shè):

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

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

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

3 算法設(shè)計(jì)

3.1 LEACH算法

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

3.2FSR算法

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

3.3 本文算法描述

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

下面對(duì)簇間進(jìn)行簡(jiǎn)單的分析。

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

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

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

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

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

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

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

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

3.4 算法性能分析

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

4 仿真與比較

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

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

5 結(jié) 語

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

參 考 文 獻(xiàn)

［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)絡(luò)\\[M\\].北京:清華大學(xué)出版社，2005.

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

［6］任豐原，林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，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).



作者簡(jiǎn)介 方軍榮 男，1981年出生，碩士研究生。主要研究方向?yàn)樽顑?yōu)化理論與算法，無線傳感器網(wǎng)絡(luò)。

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

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>