馬簫雯,余 翔,許 未
(重慶郵電大學(xué)電信增值業(yè)務(wù)研究所,重慶400065)
隨著無線通信技術(shù)以及傳感器技術(shù)的飛速發(fā)展,由具有感知能力、計(jì)算能力和通信能力節(jié)點(diǎn)組成的無線傳感器網(wǎng)絡(luò)[1-2]的研究越來越受到研究人員的重視。組成傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)包括數(shù)據(jù)匯聚節(jié)點(diǎn)(sink)和普通的傳感器節(jié)點(diǎn)。由于傳感器節(jié)點(diǎn)能量有限,在進(jìn)行傳感器網(wǎng)絡(luò)路由研究的時(shí)候,降低能耗使得無線傳感器網(wǎng)絡(luò)的整體存活時(shí)間延長是需要考慮的[3]。
低功耗自適應(yīng)聚類路由協(xié)議[4](Low Energy Adaptive Clustering Hierarchy,LEACH)是無線傳感器網(wǎng)絡(luò)中一種經(jīng)典的分層次路由協(xié)議,算法通過循環(huán)隨機(jī)地選取簇首節(jié)點(diǎn)來提高網(wǎng)絡(luò)的能量利用率和延長系統(tǒng)的生命周期。相對(duì)于無線傳感器網(wǎng)絡(luò)的傳統(tǒng)平面靜態(tài)路由協(xié)議,LEACH可以將網(wǎng)絡(luò)生存時(shí)間延長接近15%[5]。但是,LEACH協(xié)議在簇首選擇采用的是各個(gè)節(jié)點(diǎn)等概率隨機(jī)成為簇首的方式,沒有考慮到節(jié)點(diǎn)的能量以及簇首與基站的距離等因素,而這些因素恰恰可能導(dǎo)致所選擇的簇首不是最優(yōu),從而影響到整個(gè)網(wǎng)絡(luò)的性能。針對(duì)LEACH協(xié)議存在的一些不足,提出一些改進(jìn)建議,并針對(duì)其中的部分建議做了仿真驗(yàn)證,所采取的措施有效地提高了節(jié)點(diǎn)的能量利用率同時(shí)也延長了整個(gè)網(wǎng)絡(luò)的生命周期。
LEACH路由協(xié)議是Heinzelman(MIT,電子與計(jì)算系)于2000年為WSN設(shè)計(jì)的基于分層的低功耗自適應(yīng)聚類路由算法。LEACH協(xié)議的工作過程被劃分為周期性的“輪”,每輪包括成簇和數(shù)據(jù)傳輸兩個(gè)階段。在成簇階段,節(jié)點(diǎn)之間首先按照一定的策略進(jìn)行簇首選舉,等到簇首節(jié)點(diǎn)確定之后,將向全網(wǎng)廣播自身本輪擔(dān)任簇首的消息,其他節(jié)點(diǎn)根據(jù)接收到的廣播信號(hào)的強(qiáng)度來決定本輪所要加入的簇,最后,簇首節(jié)點(diǎn)接收加入請(qǐng)求消息并創(chuàng)建TDMA和CDMA編碼機(jī)制。在數(shù)據(jù)傳輸階段,簇首節(jié)點(diǎn)首先接收簇內(nèi)成員節(jié)點(diǎn)采集的監(jiān)測(cè)數(shù)據(jù),然后對(duì)接收到的數(shù)據(jù)和自身的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合,最終將融合后的數(shù)據(jù)發(fā)送給基站[6]。
簇首節(jié)點(diǎn)的選取是LEACH算法的核心組成部分,這部分在整個(gè)LEACH協(xié)議中占有很重要的位置,其具體的選擇策略描述如下:在成簇階段,每個(gè)傳感器節(jié)點(diǎn)產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù),如若該數(shù)小于某一個(gè)閥值Pi(t),則向全網(wǎng)通告自己本輪擔(dān)任簇首的消息;若該節(jié)點(diǎn)之前已經(jīng)擔(dān)任過簇首,則將閥值Pi(t)設(shè)置為0,表明本輪不再擔(dān)任簇首;反之,如果節(jié)點(diǎn)之前沒有擔(dān)任過簇首,則在本輪中以閥值Pi(t)為概率競(jìng)選簇首;當(dāng)網(wǎng)絡(luò)中只剩下一個(gè)節(jié)點(diǎn)沒有擔(dān)任過簇首時(shí),該節(jié)點(diǎn)將把閥值Pi(t)設(shè)為1,表明自己本輪無條件的成為簇首。其中Pi(t)的計(jì)算公式如下:
式中,Ci(t)表示節(jié)點(diǎn)i在最近rmod(N/k)輪是否擔(dān)當(dāng)過簇首節(jié)點(diǎn),若擔(dān)當(dāng)過簇首,則Ci(t)=0,否則Ci(t)=1;k表示網(wǎng)絡(luò)中簇首節(jié)點(diǎn)的個(gè)數(shù),在一個(gè)已知的目標(biāo)區(qū)域內(nèi),面積為M×M,傳感器節(jié)點(diǎn)總數(shù)為N,節(jié)點(diǎn)均勻分布在檢測(cè)區(qū)域中,即 ρ=(1/(M2/k))??梢酝ㄟ^下面公式推導(dǎo)出網(wǎng)絡(luò)中最優(yōu)的分簇個(gè)數(shù):
式(2)、式(3)、式(4)中:εfs和 εmp表示無線能量模型中的參數(shù);dtoCH是簇內(nèi)成員節(jié)點(diǎn)到簇首節(jié)點(diǎn)的距離;Etotal表示總共消耗的能量;dtoBS表示簇首節(jié)點(diǎn)到基站之間的距離;Eelec表示發(fā)射電路和接收電路所消耗的能量;EDA表示節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合所消耗的能量。
在每輪的穩(wěn)定階段,傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)傳送到簇首節(jié)點(diǎn)。簇首節(jié)點(diǎn)對(duì)采集的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合后再將信息傳送給匯聚中心,匯聚中心將數(shù)據(jù)傳送給監(jiān)控中心來進(jìn)行數(shù)據(jù)的處理。穩(wěn)定階段持續(xù)一段時(shí)間之后,網(wǎng)絡(luò)重新進(jìn)行簇的建立階段,也就是進(jìn)行下一輪的簇重建,這樣不斷地循環(huán)。
LEACH的不足在于,每輪進(jìn)行都要選擇簇頭并劃分簇,并且簇頭需要一直處于醒著的狀態(tài)以接收數(shù)據(jù),這樣系統(tǒng)開銷較大,離散式區(qū)域算法對(duì)節(jié)點(diǎn)位置等要求不高,雖然能夠通過公式推導(dǎo)出可能的分簇?cái)?shù)目,但無法確定最優(yōu)的簇?cái)?shù)目。LEACH采用TDMA的MAC層機(jī)制,而事實(shí)上,在分配給節(jié)點(diǎn)的每個(gè)時(shí)隙,節(jié)點(diǎn)并不是都有數(shù)據(jù)要發(fā)送給簇頭,這樣的通信機(jī)制不能有效利用帶寬,浪費(fèi)了能量。LEACH還要求節(jié)點(diǎn)之間以及節(jié)點(diǎn)與sink之間都可以直接通信,因此局限了網(wǎng)絡(luò)的可擴(kuò)展性[7,8]。
LEACH以循環(huán)的方式隨機(jī)選取簇首,將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中,從而降低能源消耗,提高網(wǎng)絡(luò)整體生存時(shí)間。由于冗余數(shù)據(jù)被大量消除,因而在能耗方面有較好的性能。但LEACH仍存在如下不足之處。首先,LEACH算法是由網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)自組織的形成簇,簇首的選擇具有極大的隨機(jī)性。在該算法中進(jìn)行簇首選擇時(shí)沒有考慮節(jié)點(diǎn)的剩余能量、周圍鄰節(jié)點(diǎn)的數(shù)目以及已經(jīng)擔(dān)任過簇首的次數(shù)等因素,這樣會(huì)加重簇首的負(fù)擔(dān),使能耗不均[9]。當(dāng)一個(gè)節(jié)點(diǎn)做簇首的次數(shù)過多時(shí),不但自身的能量消耗加大,而且會(huì)使得距離自身較遠(yuǎn)的節(jié)點(diǎn)消耗較多的能量,不利于整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)能量的均衡和網(wǎng)絡(luò)壽命的延長;其次,不同的簇首數(shù)目也會(huì)影響到整個(gè)網(wǎng)絡(luò)的生存時(shí)間,LEACH算法簇首選擇的隨機(jī)性導(dǎo)致簇首數(shù)目的不確定。
基于以上LEACH算法在簇首選擇過程中的不足,對(duì)算法進(jìn)行改進(jìn),改進(jìn)后的算法跟LEACH算法采用相同的網(wǎng)絡(luò)要求。
2.2.1 LEACH_NEW設(shè)計(jì)思路
根據(jù)上文中所指出的LEACH算法在簇首選擇方面存在的問題,對(duì)LEACH算法做如下改進(jìn):
①靜態(tài)分簇,在第一輪簇首選擇之前根據(jù)節(jié)點(diǎn)位置情況進(jìn)行靜態(tài)分簇,并且之后不再重新分簇,只在該簇內(nèi)選擇最佳節(jié)點(diǎn)成為本簇的簇首節(jié)點(diǎn),簇首節(jié)點(diǎn)在廣播自己成為簇首的信息時(shí)也只是向本簇內(nèi)的成員節(jié)點(diǎn)廣播,不需要全網(wǎng)廣播,大大減小了節(jié)點(diǎn)的能量消耗;
②在簇首選擇過程中,將節(jié)點(diǎn)的剩余能量和網(wǎng)絡(luò)的平均能量作為參數(shù)考慮,對(duì)閥值的計(jì)算公式進(jìn)行改進(jìn),使得選出的簇首節(jié)點(diǎn)更加有利于網(wǎng)絡(luò)能耗的均衡以及整個(gè)網(wǎng)絡(luò)的生存;
③在數(shù)據(jù)傳輸階段,利用參數(shù)記錄簇頭節(jié)點(diǎn)的鄰簇頭節(jié)點(diǎn)的數(shù)目、簇頭到基站的最佳跳數(shù)和剩余能量,以便在多跳傳輸時(shí)簇頭節(jié)點(diǎn)能夠選擇更合適的下一跳節(jié)點(diǎn)并且減小節(jié)點(diǎn)的能耗。
2.2.2 LEACH_NEW的工作過程
LEACH_NEW的工作過程與LEACH一樣,也分為3個(gè)階段。即簇首的選擇階段、簇形成階段和數(shù)據(jù)傳輸階段。
首先由于考慮到每一輪重新建立簇過程中所有節(jié)點(diǎn)消耗的能量,本文算法在算法執(zhí)行開始時(shí)先采用靜態(tài)分簇方式,在初始過程中節(jié)點(diǎn)就將簇分好,并進(jìn)行相應(yīng)的優(yōu)化。之后簇內(nèi)的節(jié)點(diǎn)不再發(fā)生變化,每一輪簇首的選擇更新都在原簇內(nèi)進(jìn)行,這樣減少了每一輪之前分簇時(shí)節(jié)點(diǎn)所消耗的不必要的能量。
①在第一輪簇首選擇階段,若按照式(1)得到的閥值選擇簇首,就會(huì)出現(xiàn)簇首選擇不當(dāng)?shù)膯栴}。所以改進(jìn)算法利用新的閥值計(jì)算公式如下:
式中,Ecurrent表示節(jié)點(diǎn)的當(dāng)前能量,Einitial為節(jié)點(diǎn)的初始能量,Nneighbour表示節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù)目,CHtime表示節(jié)點(diǎn)在之前的輪中被選為簇首的次數(shù)。
②簇形成階段,經(jīng)過簇首選擇階段已經(jīng)選出了網(wǎng)絡(luò)中擔(dān)任簇首的節(jié)點(diǎn),隨后每個(gè)簇首節(jié)點(diǎn)利用CSMA協(xié)議向自己管轄范圍內(nèi)的所有剩余節(jié)點(diǎn)以相同的傳輸能量發(fā)送自己是簇首的消息,通過該消息廣播告知本簇內(nèi)的成員節(jié)點(diǎn)自己成為簇首;接著簇內(nèi)的剩余節(jié)點(diǎn)將會(huì)接受到來自簇首的消息,不過簇內(nèi)節(jié)點(diǎn)可能會(huì)在一定間隔內(nèi)收到多個(gè)這種消息,應(yīng)為鄰簇間存在干擾,在這種情況下節(jié)點(diǎn)根據(jù)接收消息的強(qiáng)度來選擇簇首,然后再?zèng)Q定加入哪個(gè)簇。
每個(gè)節(jié)點(diǎn)加入相應(yīng)的簇的同時(shí),同樣采用非持續(xù)CSMA協(xié)議向相應(yīng)的簇首發(fā)送入簇消息,包括自身的ID號(hào)。當(dāng)簇首接收所有簇內(nèi)節(jié)點(diǎn)發(fā)來的該消息時(shí),根據(jù)成員節(jié)點(diǎn)的數(shù)目,采用TDMA方式為每個(gè)簇成員分配發(fā)送數(shù)據(jù)的時(shí)隙。每個(gè)節(jié)點(diǎn)只在屬于自己的時(shí)間內(nèi)發(fā)送數(shù)據(jù),在其他時(shí)間處于休眠狀態(tài),這樣做也是為了減少節(jié)點(diǎn)的總能耗。
③數(shù)據(jù)傳輸階段,采用多跳和單跳相結(jié)合的方式。在簇內(nèi)采用單跳方式傳輸,在簇首與基站之間則分情況決定采用哪種傳輸方式。利用參數(shù)記錄簇頭節(jié)點(diǎn)的鄰簇頭節(jié)點(diǎn)的數(shù)目和剩余能量,若距離基站較近時(shí)就要避免多跳的路由機(jī)制,以減少路由的開銷。當(dāng)傳輸距離較大時(shí),通過記錄的鄰簇頭數(shù)目、跳數(shù)以及鄰簇首的剩余能量選擇最佳的一個(gè)下一跳節(jié)點(diǎn),采用多跳傳輸機(jī)制,減少網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)能耗,同時(shí)由于考慮了跳數(shù)因素,盡量減少簇首到基站的跳數(shù),以節(jié)約中間節(jié)點(diǎn)的能耗。
本文仿真工具采用網(wǎng)絡(luò)仿真工具 NS2[10,11]進(jìn)行仿真。NS2是一種可擴(kuò)展的、容易配置的和可編程的時(shí)間驅(qū)動(dòng)網(wǎng)絡(luò)仿真工具,是由美國加州的LNBL網(wǎng)絡(luò)研究組于1989年開始研究開發(fā)的軟件。NS2源代碼全部公開,提供開放的網(wǎng)絡(luò)接口。本文的仿真環(huán)境:節(jié)點(diǎn)為100個(gè)并且隨機(jī)分布在100 m×100 m的監(jiān)測(cè)區(qū)域內(nèi),Sink節(jié)點(diǎn)的位置(50,100),消息長度為500 byte,信息包的長度為25 byte,每一輪的時(shí)間為20 s,即節(jié)點(diǎn)每隔20 s的時(shí)間更換一次簇首,時(shí)間片的大小為0.023 s,每個(gè)節(jié)點(diǎn)的初始能量相同并且為2 J,網(wǎng)絡(luò)帶寬為2 M/s。
通過對(duì)整個(gè)網(wǎng)絡(luò)總的能耗以及網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目在LEACH和LEACH-NEW不同算法之下兩個(gè)指標(biāo)的對(duì)比,由圖1可以看出在相同時(shí)間內(nèi),LEACH-NEW算法的能量消耗少,提高了網(wǎng)絡(luò)的能量利用率,有效地延長了網(wǎng)絡(luò)的生命周期。
圖1 網(wǎng)絡(luò)中的總的耗能情況比較
由圖2可以明顯地看出改進(jìn)算法有效地延長了網(wǎng)絡(luò)的生命周期,LEACH算法在150 s已經(jīng)開始出現(xiàn)節(jié)點(diǎn)死亡,而LEACH-NEW算法在350 s才開始出現(xiàn)第一個(gè)節(jié)點(diǎn)的死亡,本文算法減少了簇頭節(jié)點(diǎn)在建立簇時(shí)能量的消耗,同時(shí)數(shù)據(jù)傳輸階段的單跳和多跳相結(jié)合也是減少了網(wǎng)絡(luò)中節(jié)點(diǎn)的總的能耗。
圖2 網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)目
無線傳感器網(wǎng)絡(luò)的路由算法一直都是研究的熱點(diǎn),在對(duì)傳統(tǒng)的LEACH算法深入研究的基礎(chǔ)上,指出存在的不足,提出改進(jìn)的算法,并利用NS2仿真工具進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明改進(jìn)算法減少了網(wǎng)絡(luò)的總能耗,有效地延長了整個(gè)網(wǎng)絡(luò)的生存時(shí)間。
[1] AKYILDIZ I F,SU W,SANKARASUBRAMANIAM Y,etal.Wireless Sensor Networks:A Survey[J].Computer Networks,2002,38(4):393-422.
[2] 孫建民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2006.
[3] KHAMFOROOSH K,KHAMFOROUSH H.A New Rounting Algorithm for Energy Reduction in Wireless Sensor Networks[J].IEEE,2009:505-509.
[4] 馬祖長,孫怡寧,梅濤.無線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào),2004,25(4):114-124.
[5] 陳志奎,倪晶晶,姜國海,等.WSN中一種基于剩余能量級(jí)別的負(fù)載均衡路由協(xié)議[J].微電子學(xué)與計(jì)算機(jī),2010,27(12):82-86.
[6] ZHANG Z,ZHANG X.Research of Improved Clustering Routing Algorithm Based on Load Balance in Wireless Sensor Networks[C]∥IET International Communication Conference on Wireless Mobile and Computing,2009:661-664.
[7] HEINZELMANW R,CHANDRAKASANA,BALAKRISHNAN H.Energy Efficient Communication Protocol for Wireless Microsensor Networks [C]∥ Proc.of HICSS'00.Los Alamitos,CA,USA:IEEE Press,2000:3005-3014.
[8] 沈波,張世永,鐘亦平.無線傳感網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào),2006,17(7):1588-1600.
[9] 王磊,施榮華.無線傳感器網(wǎng)絡(luò)路由算法的仿真研究[J].計(jì)算機(jī)仿真,2010,28(3):170-174.
[10] UCB/LBNL/VINT Network Simulator-ns(Version 2),http://www.isi.edu/nsnam/ns/,2011.
[11]徐雷鳴,龐博,趙耀.NS與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社,2008.