一種基于混沌策略的無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議

徐興東

(中南民族大學(xué)計(jì)算與實(shí)驗(yàn)中心，湖北武漢430074)

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

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

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

1 研究現(xiàn)狀

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

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

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

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

2 CLEACH路由算法

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

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

CLEACH路由算法的流程如下:

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

(2)計(jì)算種群P(g)中每個(gè)個(gè)體的適應(yīng)度值.

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

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

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

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

圖1 輪數(shù)與存活的節(jié)點(diǎn)數(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é)語(yǔ)

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

［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ú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報(bào)，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］李 磊，滕春賢.一類兩層多目標(biāo)決策的全局優(yōu)化方法［J］.哈爾濱理工大學(xué)學(xué)報(bào)，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ù)學(xué)報(bào)，2010，23(8):1173-1178.

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

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

［10］吳 迪，胡 鋼.無(wú)線傳感器網(wǎng)絡(luò)多路徑簇頭鏈分簇式路由算法［J］.計(jì)算機(jī)工程與科學(xué)，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ú)線傳感器網(wǎng)絡(luò)節(jié)能路由研究［J］.工業(yè)控制計(jì)算機(jī)，2011，24(2):1-3.