徐興東

(中南民族大學計算與實驗中心，湖北武漢430074)

無線傳感器網(wǎng)絡(WSN)是由具有傳感、數(shù)據(jù)處理和短距離無線通信等功能的傳感器組成 .WSN是一種新型的無基礎設施的無線網(wǎng)絡，能夠協(xié)作地實時監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息，并對其進行處理，通過無線通信方式把信息傳送到信息匯聚點［1］.隨著國內(nèi)外無線傳感器網(wǎng)絡的研究發(fā)展，已有許多用于無線傳感器網(wǎng)絡的路由協(xié)議.從網(wǎng)絡的拓撲結(jié)構(gòu)看可以分為兩類［2］:平面路由協(xié)議和分簇路由協(xié)議 .在平面路由協(xié)議中，所有節(jié)點的地位是平等的，不存在等級和層次的差異 .平面路由協(xié)議的優(yōu)點是簡單、具有良好的健壯性，缺點是可擴展性差;在分簇路由協(xié)議中，簇頭主要負責數(shù)據(jù)融合和將融合后的數(shù)據(jù)轉(zhuǎn)發(fā)到基站.通過約定的協(xié)議，在整個網(wǎng)絡覆蓋范圍內(nèi)選舉出一定數(shù)量的節(jié)點作為簇首，從而將網(wǎng)絡劃分為簇，它具有路由選擇、資源管理以及數(shù)據(jù)融合等功能.分簇路由協(xié)議是目前公認的最有效的組織方式.

LEACH協(xié)議__［3］是由Heinzelman等人在2000年提出的一種低功耗自適應分簇路由協(xié)議.該算法的基本思想是:通過等概率的隨機循環(huán)選擇簇頭節(jié)點，然后簇頭收集簇內(nèi)節(jié)點數(shù)據(jù)并融合，并將整個網(wǎng)絡的能量負載均衡分配到每個傳感器節(jié)點中，從而高效地使用傳感器節(jié)點有限的能量，降低網(wǎng)絡能量耗費，最大化網(wǎng)絡的生命周期［4］.LEACH在簇頭選舉時缺乏對節(jié)點當前剩余能量的考慮，單純地采用隨機方式選擇簇頭，容易出現(xiàn)“能量空洞”現(xiàn)象 .LEACH這種選舉簇頭的隨機性也會造成簇頭在網(wǎng)絡中的位置分布不佳，當簇頭位置比較集中時，簇的覆蓋區(qū)域?qū)⒊霈F(xiàn)部分重疊的現(xiàn)象，還會造成簇頭之間的無線信號干擾;當簇頭分布在邊緣區(qū)域時，簇內(nèi)的某些成員節(jié)點到簇頭的距離會變大，相應簇的能量開銷也變大.混沌是非線性系統(tǒng)獨有的一種運動形式，混沌運動具有遍歷性、隨機性、規(guī)律性等特點，能在一定范圍內(nèi)按其自身的規(guī)律不重復地遍歷所有狀態(tài).混沌優(yōu)化是一種新型搜索算法，它直接采用混沌變量對解空間進行搜索，具有對初值敏感、易于跳出局部最優(yōu)解、搜索速度快和全局漸近收斂的特點，被廣泛用于非線性優(yōu)化領域［5］.

本文在LEACH協(xié)議基礎上，利用混沌優(yōu)化的遍歷性等優(yōu)點，將混沌搜索機制引入到分簇路由協(xié)議中，并提出了一種新的無線傳感器節(jié)能算法——混沌LEACH協(xié)議(CLEACH).CLEACH協(xié)議結(jié)合了LEACH和混沌優(yōu)化的優(yōu)點，選擇采用 LEACH中的使每個區(qū)域的節(jié)點數(shù)目大致相同，然后，在同一區(qū)域中選取簇頭時采用 LEACH的簇頭選擇機制 .仿真實驗表明:該路由協(xié)議能使簇頭能量消耗更均衡，并且能有效延長WSN的壽命.

1 研究現(xiàn)狀

目前，國內(nèi)外已出現(xiàn)大量的分簇路由協(xié)議，從不同的角度來延長傳感器網(wǎng)絡的壽命 .文獻［6］提出M-LEACH協(xié)議是一種多跳LEACH算法.該協(xié)議簇內(nèi)的節(jié)點不再是以單跳的方式傳輸數(shù)據(jù)到簇頭，而是通過簇內(nèi)其他節(jié)點轉(zhuǎn)發(fā) .文獻［7］在LEACH和PEGASIS算法基礎上，提出了一種改進的有效路由LEACH-P算法.LEACH-P算法不僅改善了LEACH算法在大規(guī)模傳感器網(wǎng)絡中簇頭節(jié)點能量消耗過大的問題，而且克服了PEGASIS算法在大規(guī)模傳感器網(wǎng)絡中實時性差的問題.為有效解決無線傳感器網(wǎng)絡中的“熱區(qū)”問題，文獻［8］提出了一種能量自適應的非均勻分簇路由協(xié)議.該協(xié)議采取非均勻的分簇結(jié)構(gòu)，使靠近基站的簇范圍減小到合理的范圍 .文獻［9］提出 EEUC算法利用非均勻的競爭半徑，使得靠近匯聚點的簇的成員數(shù)目相對較小，從而簇頭能夠節(jié)約能量以供數(shù)據(jù)轉(zhuǎn)發(fā)使用，達到均衡簇頭能量消耗的目的.此外，在簇頭選擇其他節(jié)點時，不僅考慮候選節(jié)點相對匯聚點的位置，還應考慮候選節(jié)點的剩余能量.不同于LEACH，EEUC簇頭通過局部競爭的方式產(chǎn)生，同時簇頭間進行多跳數(shù)據(jù)轉(zhuǎn)發(fā).SAR協(xié)議通過構(gòu)建以sink的單跳鄰居節(jié)點為根節(jié)點的多播樹實現(xiàn)傳感器節(jié)點到vsink的多跳路徑.它的特點是路由決策不僅要考慮到每條路徑的能源，還要涉及端到端的延遲需求和待發(fā)送數(shù)據(jù)包的優(yōu)先級［10］.SPIN路由算法的目標是通過使用節(jié)點間的協(xié)商制度和資源自適應機制，解決傳統(tǒng)泛洪法存在的不足之處［11］.EARSN是基于3層體系結(jié)構(gòu)的路由協(xié)議 .該協(xié)議將網(wǎng)絡運行前由終端用戶sink將傳感器節(jié)點劃分成簇，并通知每個簇首節(jié)點的ID標識和簇內(nèi)所分配節(jié)點的位置信息［12］.在文獻［13］中，衛(wèi)琪等介紹和分析了 LEACH，PEGASIS和HEED 3種典型節(jié)能分簇路由協(xié)議，并通過對三者的綜合比較總結(jié)出現(xiàn)有分簇路由協(xié)議存在的問題，并提出相應的解決思路.這里，主要分析與本文直接相關(guān)的LEACH協(xié)議.

在LEACH協(xié)議中，每個傳感節(jié)點都有機會充當簇頭節(jié)點，簇頭節(jié)點進行輪換，以達到分散各節(jié)點能量消耗目的.簇頭節(jié)點的選擇主要依據(jù)網(wǎng)絡中所需要的簇頭節(jié)點總數(shù)和迄今為止每個節(jié)點已成為簇頭節(jié)點的次數(shù)來判定.每個傳感器節(jié)點在0～1之間隨機選擇一個數(shù)，如果選擇的數(shù)小于規(guī)定閥值T(n)，那么該節(jié)點就成為簇頭節(jié)點，并通過廣播告知整個網(wǎng)絡.網(wǎng)絡中的每個非簇頭節(jié)點根據(jù)收到信號的強度選擇要加入的簇，并通知相應的簇頭節(jié)點，自己則成為簇內(nèi)組員.T(n)的計算公式如下:

其中，p表示在無線網(wǎng)絡中簇頭節(jié)點所占的百分比，r表示當前循環(huán)次數(shù)，G是在前1/p輪中未充當過簇頭節(jié)點的集合.

LEACH協(xié)議通過設置T(n)值，以保證每個節(jié)點在1/p輪內(nèi)都有機會充當一次簇頭節(jié)點，從而平衡了節(jié)點的能量消耗 .LEACH協(xié)議提出后使得無線傳感器網(wǎng)絡性能得到很大的改善 .但是LEACH算法也存在許多不足，在剛開始假設每個節(jié)點的初始能量相同，在現(xiàn)實環(huán)境中很難做到;LEACH算法是隨機選擇一部分節(jié)點擔任簇首，每個節(jié)點成為簇首節(jié)點的概率相同，這樣可能導致一些高能量節(jié)點沒機會成為簇首節(jié)點，而一些低能量節(jié)點成為簇首節(jié)點.一旦這些低能量節(jié)點成為簇首節(jié)點，將會很快耗盡其能量.雖然降低了算法的復雜度，卻可能導致簇首都聚集在網(wǎng)絡的一角，此時大量節(jié)點都需與距離較遠的簇首通信，這樣會使這些節(jié)點負載過重而較早死亡;簇首節(jié)點在通信過程中采用單跳與基站通信，這樣就會導致較遠的簇首節(jié)點能量消耗過大，而過早死亡，影響整個網(wǎng)絡的性能 .由于LEACH協(xié)議假定所有節(jié)點能夠與匯聚節(jié)點直接通信，并且每個節(jié)點都具備支持不同MAC協(xié)議的計算能力，因此該方法不適合在大規(guī)模的無線傳感器網(wǎng)絡中應用.

2 CLEACH路由算法

混沌優(yōu)化算法的基本思想是將混沌狀態(tài)引入到優(yōu)化變量中，并把混沌運動的遍歷范圍“放大”到優(yōu)化變量的取值空間，然后利用混沌變量搜索.我們利用Logistic混沌映射，即:

g:βk=αβk－1(1－βk－1)，βk∈［0，1］，k=1，2，… .其中，α為吸引子，當α=4時，Logistic混沌映射為滿映射，系統(tǒng)處于完全混沌狀態(tài).我們利用混沌變量對初值的敏感性，賦n個微小差異的初值，得到n個混沌變量，并將它們作為CLEACH算法的初始種群.

CLEACH路由算法的流程如下:

(1)初始化控制參數(shù).隨機選取m個長度為1的二進制位串為初值，混沌迭代次數(shù)g=1，混沌擾動概率p，混沌吸引子α.

(2)計算種群P(g)中每個個體的適應度值.

(3)對種群P(g)進行選擇操作，將適應度較大的個體保留到下一代，得到新的群體P'(g).

(4)對群體P'(g)中的個體進行混沌擾動操作.以混沌擾動概率p選取要進行混沌擾動的個體的每一個分量.設xi對應取值范圍是［ai，bi］，那么經(jīng)過混沌擾動操作后，xi=ai+α(bi－ai)βk(1－βk)，其中，βk是Logistic混沌映射為混沌初始值.經(jīng)過混沌擾動操作后，得到下一代群體P(g+1).

(5)當g≥500時，算法自然結(jié)束，輸出最優(yōu)解;否則，g=g+1，返回到步驟(2).

3 仿真實驗與結(jié)果分析

本文用Matlab對CLEACH路由協(xié)議進行仿真測試.選擇節(jié)點分布在200m×200m的區(qū)域內(nèi)，節(jié)點數(shù)N=200，基站位于(0，0)處 .每個節(jié)點的初始能量為0.5J，數(shù)據(jù)包大小為4000bit.

圖1、2表示的是實驗仿真結(jié)果 .從圖1中不難看出，CLEACH路由協(xié)議中的第一個節(jié)點死亡的時間大概是900輪，LEACH和M-LEACH路由協(xié)議中的第一個節(jié)點死亡的時間分別是600輪和800輪，由此可見，CLEACH路由協(xié)議延長了第一個節(jié)點的死亡時間.圖2表示的是在CLEACH路由協(xié)議和LEACH路由協(xié)議中簇頭能量消耗 .CLEACH遠低于LEACH.因為在LEACH協(xié)議中，簇頭采用單跳通信將數(shù)據(jù)發(fā)往基站，同時由于簇頭數(shù)目不穩(wěn)定，導致簇頭能耗消耗增大.而CLEACH采用多跳通信，節(jié)省了很多能量 .在 CLEACH中為候選節(jié)點設置一個等待時間，使它們按照次序傳送報文 .在傳播的過程中，同時完成簇的建立以及簇間通信，CLEACH協(xié)議的這個過程花費的開銷也很低.

圖1 輪數(shù)與存活的節(jié)點數(shù)比較Fig.1 Compare of the number of rounds and nodes alive

圖2 基站收到的數(shù)據(jù)量比較Fig.2 Compare of the amount of data received by the base station

4 結(jié)語

無線傳感器網(wǎng)絡的路由協(xié)議是無線傳感器網(wǎng)絡研究中的熱點和焦點問題.本文采用CLEACH路由算法，減小簇間多跳能量的消耗，從而延長了網(wǎng)絡的生存時間.CLEACH協(xié)議從候選節(jié)點根據(jù)各自的等待時間按照一定的次序發(fā)送廣播報文來競爭簇頭，簇頭選出后普通節(jié)點根據(jù)最近的簇頭加入簇，為了進一步減少能量消耗和維持節(jié)點能量均衡，遠離基站的簇頭.實驗結(jié)果表明:CLEACH協(xié)議通過多跳的方式經(jīng)過其他簇頭，將收集的數(shù)據(jù)傳送到基站，從而有效提高網(wǎng)絡性能.

［1］Younis M，YoussefM，Arisha K.Energy aware routing in cluster-based sensor networks［C］//The 10th IEEE International Symposium on Modeling Analysis and Simulation of Computer and Telecommunications Systems.Beijing:IEEE，2002:129-136.

［2］沈 波，張世永，鐘亦平.無線傳感器網(wǎng)絡分簇路由協(xié)議［J］.軟件學報，2006，17(7):1588-1600.

［3］Fan Yiming，Yu Jianjun.The communication protocol for wireless sensor network about LEACH［C］//CISW.Proceedings of 2007 International Conference on Computation Intelligence and Security Workshops.Mexico:CISW，2007:550-553.

［4］Cardei M，Wu J.Energy-efficient coverage problems in wireless Ad Hoc sensor networks ［J］.Computer Communications，2006，29(4):413-420.

［5］李 磊，滕春賢.一類兩層多目標決策的全局優(yōu)化方法［J］.哈爾濱理工大學學報，200l，6(6):25-28.

［6］Heinzelman W R，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless micro sensor networks［J］.IEEE Transactions on Wireless Networking，2002，1(4):660-670.

［7］張 震，閆連山，潘 煒，等.基于LEACH和PEGASIS的簇頭成鏈可靠路由協(xié)議研究［J］.傳感技術(shù)學報，2010，23(8):1173-1178.

［8］李樹華，劉振宇，李迎秋.能量自適應的無線傳感器網(wǎng)絡分簇路由協(xié)議［J］.計算機工程與設計，2010，31(3):504-507.

［9］李成法，陳貴海.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議［J］.計算機學報，2007，30(1):88-91.

［10］吳 迪，胡 鋼.無線傳感器網(wǎng)絡多路徑簇頭鏈分簇式路由算法［J］.計算機工程與科學，2008，30(6):101-105.

［11］SohrabiK，Gao J，Ailawadhi V，etal，Protocols for selforganization of a wireless sensor network［J］.IEEE Personal Communications，2000，5(7):16-27.

［12］Kulik J，Heinzelman W R，Balakrishnan H.Negotiation based protocols for disseminating information in wireless sensor networks［J］. Wireless Networks，2002，8(223):169-185.

［13］衛(wèi) 琪，馬 禮.無線傳感器網(wǎng)絡節(jié)能路由研究［J］.工業(yè)控制計算機，2011，24(2):1-3.