能量感知的WSN節(jié)點(diǎn)分類控制路由算法*

劉 群，白全煒，曾憲華，王 亮

(重慶郵電大學(xué)計(jì)算機(jī)學(xué)院，重慶 400065)

無(wú)線傳感器網(wǎng)絡(luò)(WSN)是一種新型的無(wú)線通信網(wǎng)絡(luò)，它融合了通信技術(shù)，嵌入式計(jì)算技術(shù)和傳感器技術(shù)，由大量的傳感器節(jié)點(diǎn)通過(guò)無(wú)線介質(zhì)連接構(gòu)成，采用自組織的形式配置微型的智能傳感器節(jié)點(diǎn)，通過(guò)節(jié)點(diǎn)的協(xié)同工作來(lái)采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中目標(biāo)信息。傳感器節(jié)點(diǎn)通常由電池供電，而且在一些應(yīng)用環(huán)境下更換電池或者對(duì)電池進(jìn)行充電是不可行的，所以如何高效，合理地使用能源，盡可能地延長(zhǎng)網(wǎng)絡(luò)的生命期，成為了傳感器網(wǎng)絡(luò)研究的核心問(wèn)題之一［1－3］。

路由協(xié)議在無(wú)線傳感器網(wǎng)絡(luò)中起著相當(dāng)重要的作用，并且其能量消耗也是網(wǎng)絡(luò)消耗中的主要部分，因此設(shè)計(jì)一種有效的路由協(xié)議是減少網(wǎng)絡(luò)能量消耗的關(guān)鍵。目前在無(wú)線傳感器網(wǎng)絡(luò)中，路由協(xié)議分為三類:平面路由、分層路由以及能量感知路由。

在平面路由中所有節(jié)點(diǎn)具有相同的地位和功能，它們通過(guò)相互之間的局部操作和信息反饋來(lái)生成路由。平面路由的優(yōu)點(diǎn)是簡(jiǎn)單、易擴(kuò)散，無(wú)須進(jìn)行任何結(jié)構(gòu)維護(hù)工作，不易產(chǎn)生瓶頸效應(yīng)，因此具有較好的健壯性，典型的平面路由有Flooding Routing［4］，DD(directed diffusion)［5］，SPIN(sensor protocols for information via negotiation)［6］等。平面路由的最大缺點(diǎn)在于:網(wǎng)絡(luò)中無(wú)管理節(jié)點(diǎn)，缺乏對(duì)通信資源的優(yōu)化管理，對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化的反應(yīng)速度較慢等。

在分層路由中，LEACH算法［7］是第一個(gè)基于多簇結(jié)構(gòu)的路由算法，其成簇思想貫穿于其后提出的多個(gè)算法中，但是也存在著不足。如在簇頭選舉的過(guò)程中沒有考慮到節(jié)點(diǎn)的剩余能量，可能能量較低的節(jié)點(diǎn)被選為簇頭，導(dǎo)致該節(jié)點(diǎn)過(guò)早死亡。HEED算法［8］在選擇簇頭時(shí)考慮了節(jié)點(diǎn)的剩余能量，但需要在一定的迭代次數(shù)內(nèi)與周圍鄰居節(jié)點(diǎn)不斷地進(jìn)行信息交互，因此算法的實(shí)現(xiàn)需要額外的通信代價(jià)。PEGASIS［9］則將節(jié)點(diǎn)組織成鏈的形式，鏈的形成由每一個(gè)節(jié)點(diǎn)或者基站計(jì)算得到，因此需要知道網(wǎng)絡(luò)拓?fù)涞娜中畔ⅰ?/p>

隨著無(wú)線傳感器網(wǎng)絡(luò)研究的深入，路由協(xié)議的研究已從當(dāng)初避免網(wǎng)絡(luò)擁塞和保持網(wǎng)絡(luò)連通性等方面，轉(zhuǎn)而重點(diǎn)研究提高整個(gè)網(wǎng)絡(luò)的利用率、平衡網(wǎng)絡(luò)流量和能耗、減小通信延時(shí)等方面，而能量感知路由則代表著該研究方向。

文獻(xiàn)［10］提出了一種能量感知路由協(xié)議，EAR(Energy Aware Routing，簡(jiǎn)稱EAR)協(xié)議。在該協(xié)議中，源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立多條通信路徑，每條路由都具有一個(gè)與節(jié)點(diǎn)剩余能量有關(guān)的選擇概率，當(dāng)源節(jié)點(diǎn)需要向目的節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)，協(xié)議根據(jù)路徑的選擇概率選擇一條路徑進(jìn)行數(shù)據(jù)傳輸。但該機(jī)制沒有考慮對(duì)距離(跳數(shù))的優(yōu)化，且需周期性地實(shí)施洪泛查詢來(lái)進(jìn)行路由維護(hù)，增加協(xié)議開銷。

文獻(xiàn)［11］提出的GEAR協(xié)議根據(jù)地理位置信息，建立Sink到監(jiān)測(cè)區(qū)域的優(yōu)化路徑，支持Sink向監(jiān)測(cè)區(qū)所有節(jié)點(diǎn)發(fā)送查詢命令，避免了洪泛傳播方式，減少了路由建立的開銷。GEAR把節(jié)點(diǎn)到監(jiān)測(cè)區(qū)域的距離和節(jié)點(diǎn)剩余能量定義為估計(jì)路由代價(jià)，并利用捎帶機(jī)制獲取實(shí)際路由代價(jià)，進(jìn)行數(shù)據(jù)傳輸?shù)穆窂絻?yōu)化，形成能量高效的傳輸路徑。協(xié)議雖然實(shí)現(xiàn)了節(jié)點(diǎn)間的負(fù)載均衡，但在異構(gòu)網(wǎng)絡(luò)中，初始能量較少的節(jié)點(diǎn)會(huì)較早耗盡能量而失效，影響整個(gè)網(wǎng)絡(luò)的性能。并且隨著網(wǎng)絡(luò)中建立的路由不斷增加，在路由方向上的節(jié)點(diǎn)耗能增大，其選擇代價(jià)增大，相應(yīng)地，路由方向以外的節(jié)點(diǎn)會(huì)被優(yōu)先選擇，從而出現(xiàn)數(shù)據(jù)在多個(gè)能量旺盛的節(jié)點(diǎn)間跳轉(zhuǎn)的現(xiàn)象，稱為“折線效應(yīng)”，其直接的后果就是數(shù)據(jù)傳輸?shù)难訒r(shí)增加，網(wǎng)絡(luò)總能耗增大。

針對(duì)GEAR協(xié)議的不足之處，本文提出了一種新的能量感知的WSN節(jié)點(diǎn)分類控制路由算法CEAR(Classifying Control-based Energy Aware Routing Algorithm fornodesin WirelessSensorNetworks，CEAR)。算法首先定義了能量閾值把普通節(jié)點(diǎn)分為骨干節(jié)點(diǎn)和獨(dú)立節(jié)點(diǎn)，從而保護(hù)初始能量較少的節(jié)點(diǎn)。然后骨干節(jié)點(diǎn)通過(guò)建立骨干路由樹來(lái)傳輸數(shù)據(jù)，獨(dú)立節(jié)點(diǎn)則根據(jù)周圍鄰居節(jié)點(diǎn)的不同情況采用不同的選擇函數(shù)進(jìn)行下一跳路由;針對(duì)部分獨(dú)立節(jié)在傳輸數(shù)據(jù)時(shí)會(huì)出現(xiàn)“折線效應(yīng)”，算法采用了自適應(yīng)調(diào)整策略，從而消除此折線效應(yīng)，提高了數(shù)據(jù)傳輸?shù)臅r(shí)效性，節(jié)約了網(wǎng)絡(luò)總能耗。

論文余下部分結(jié)構(gòu)如下:第1部分主要是介紹無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu);第2部分從能量閾值、骨干路由樹的建立以及獨(dú)立節(jié)點(diǎn)的路由選擇三個(gè)大的方面具體闡述本文算法;第3部分通過(guò)實(shí)驗(yàn)驗(yàn)證CEAR算法在均衡節(jié)點(diǎn)能量消耗，傳送數(shù)據(jù)包和延時(shí)方面都優(yōu)于GEAR算法;第4部分為總結(jié)與展望。

1 WSN拓?fù)浣Y(jié)構(gòu)描述

無(wú)線傳感器網(wǎng)絡(luò)沒有底層基礎(chǔ)設(shè)施。在傳感器被放置到監(jiān)測(cè)環(huán)境后，傳感器自行組織構(gòu)成網(wǎng)絡(luò)。其基本網(wǎng)絡(luò)拓?fù)淇煞譃?3種［12］，分別是基于簇(Cluster)的分層結(jié)構(gòu)、基于網(wǎng)(Mesh)的平面結(jié)構(gòu)和基于鏈(Chain)的線結(jié)構(gòu)，其各自的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 自組織無(wú)線傳感器網(wǎng)絡(luò)拓?fù)鋱D

基于簇的分層結(jié)構(gòu)具有天然的分布式處理能力，簇頭就是分布式處理中心，每個(gè)簇成員都把數(shù)據(jù)傳給簇頭，在簇頭完成數(shù)據(jù)處理和融合，然后由其他簇頭多跳轉(zhuǎn)發(fā)或直接傳給用戶節(jié)點(diǎn)，簇中的成員是輪流或者每次選擇剩余能量最多的成員做簇頭。基于網(wǎng)的平面結(jié)構(gòu)傳感器節(jié)點(diǎn)連成一張網(wǎng)，網(wǎng)絡(luò)健壯性強(qiáng)，且傳輸可靠性非常高，個(gè)別鏈路和傳感器節(jié)點(diǎn)發(fā)生失效時(shí)，不會(huì)引起網(wǎng)絡(luò)分立，可以同時(shí)通過(guò)多條信源信宿間路由傳輸數(shù)據(jù)?；阪湹木€性結(jié)構(gòu)傳感器節(jié)點(diǎn)被串聯(lián)在一條或多條鏈上，鏈尾與Sink節(jié)點(diǎn)相連。

2 CEAR路由算法

2.1 能量閾值

Sink節(jié)點(diǎn)需要周期性地探測(cè)網(wǎng)絡(luò)的能量情況來(lái)生成能量閾值，但探測(cè)整個(gè)網(wǎng)絡(luò)所有節(jié)點(diǎn)的能量情況會(huì)給網(wǎng)絡(luò)帶來(lái)更大負(fù)擔(dān)，所以Sink節(jié)點(diǎn)只探測(cè)周圍鄰居節(jié)點(diǎn)的能量情況，來(lái)近似估計(jì)整個(gè)網(wǎng)絡(luò)的能量情況，從而生成能量閾值。

定義1能量閾值(Energy Threshold):Sink節(jié)點(diǎn)首先對(duì)周圍鄰居節(jié)點(diǎn)的剩余能量進(jìn)行探測(cè)［13］，統(tǒng)計(jì)并計(jì)算各鄰居節(jié)點(diǎn)剩余能量的均值，該均值為本文的能量閾值，即記

其中，Ni為sink節(jié)點(diǎn)周圍的第i個(gè)鄰居節(jié)點(diǎn)，n為鄰居節(jié)點(diǎn)個(gè)數(shù)為第i個(gè)鄰居節(jié)點(diǎn)的剩余能量。

定義2骨干節(jié)點(diǎn)(Mainstay Node，記作MN):如果任意普通節(jié)點(diǎn)Ni有Es(Ni)≥ET，那么該普通節(jié)點(diǎn)Ni屬于骨干節(jié)點(diǎn)。其中，Es(Ni)表示節(jié)點(diǎn)Ni自身的剩余能量。

定義 3獨(dú)立節(jié)點(diǎn)(Independent Node，記作IN):如果任意普通節(jié)點(diǎn)Nj有Es(Nj)＜ET，那么該普通節(jié)點(diǎn)Nj屬于獨(dú)立節(jié)點(diǎn)。其中，Es(Nj)表示節(jié)點(diǎn)Nj自身的剩余能量。

2.2 建立骨干路由樹

匯聚節(jié)點(diǎn)通過(guò)廣播路徑建立消息，各節(jié)點(diǎn)對(duì)廣播報(bào)文內(nèi)的信息和自身信息進(jìn)行判斷，建立骨干路由樹［14］，從而形成數(shù)據(jù)的主要傳輸路徑。具體步驟如下:

(1)如果節(jié)點(diǎn)是匯聚節(jié)點(diǎn)，則通過(guò)發(fā)送MYAGENT_ASK報(bào)文對(duì)鄰居節(jié)點(diǎn)的能量情況進(jìn)行探測(cè)，并準(zhǔn)備接收MYAGENT_ANSWER報(bào)文，從而近似估計(jì)出整個(gè)網(wǎng)絡(luò)的能量情況。

(2)如果傳感器節(jié)點(diǎn)收到MYAGENT_ASK報(bào)文，則回復(fù)MYAGENT_ANSWER報(bào)文來(lái)報(bào)告自身能量情況。

(3)匯聚節(jié)點(diǎn)通過(guò)接收MYAGENT_ANSWER報(bào)文來(lái)獲得鄰居節(jié)點(diǎn)的能量，將這些節(jié)點(diǎn)及其能量寫入MYAGENT_ENERGY緩沖區(qū)，并通過(guò)計(jì)算均值來(lái)獲得能量閾值。

(4)匯聚節(jié)點(diǎn)將能量閾值放入到MYAGENT_BROAD報(bào)文中，對(duì)網(wǎng)絡(luò)進(jìn)行廣播。

(5)如果普通傳感器節(jié)點(diǎn)收到 MYAGENT_BROAD報(bào)文，首先將自身剩余能量與ET進(jìn)行比較，如果小于ET，則節(jié)點(diǎn)被判定為獨(dú)立節(jié)點(diǎn)，轉(zhuǎn)向(6)。否則，通過(guò)到匯聚節(jié)點(diǎn)的跳數(shù)來(lái)決定是否將該節(jié)點(diǎn)放入骨干路由樹中。如果通過(guò)判斷該節(jié)點(diǎn)能夠加入到骨干路由樹中，則轉(zhuǎn)向(8)，否則繼續(xù)等待其他節(jié)點(diǎn)發(fā)送的MYAGENT_BROAD報(bào)文。

(6)當(dāng)節(jié)點(diǎn)被判定為獨(dú)立節(jié)點(diǎn)時(shí)，就會(huì)定時(shí)發(fā)出MYAGENT_RREQ報(bào)文，對(duì)鄰居節(jié)點(diǎn)的情況進(jìn)行探測(cè)，并準(zhǔn)備接收MYAGENT_RREP報(bào)文，將鄰居節(jié)點(diǎn)情況寫入MYAGENT_RARRAY緩沖區(qū)。

(7)如果節(jié)點(diǎn)收到MYAGENT_RREQ報(bào)文，則回復(fù)MYAGENT_RREP報(bào)文，來(lái)報(bào)告自身的路由情況。

(8)當(dāng)節(jié)點(diǎn)被判定可以加入到骨干路由樹中，將其在樹中的父節(jié)點(diǎn)的信息寫入father緩沖區(qū)，判斷該路徑上的最小PA(power Available)，并把MYAGENT_BROAD報(bào)文中的rp_hop項(xiàng)加1，繼續(xù)向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)該報(bào)文。

(9)所有節(jié)點(diǎn)都不停的準(zhǔn)備接收各種MYAGENT報(bào)文，當(dāng)不再有MYAGENT報(bào)文發(fā)送和接收時(shí)，骨干路由樹建立過(guò)程結(jié)束，得到的網(wǎng)絡(luò)結(jié)構(gòu)圖如圖2所示。

圖2 網(wǎng)絡(luò)結(jié)構(gòu)圖

利用路由樹生成算法建立骨干路由樹，該建樹過(guò)程融入了源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小跳數(shù)算法［15］，骨干節(jié)點(diǎn)通過(guò)骨干路由樹進(jìn)行數(shù)據(jù)傳輸，由此可知，骨干節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)不會(huì)出現(xiàn)“折線效應(yīng)”。

2.3 獨(dú)立節(jié)點(diǎn)的路由選擇

2.3.1 能量效用選擇函數(shù)

如果節(jié)點(diǎn)是IN，則要對(duì)鄰居節(jié)點(diǎn)進(jìn)行周期性的信息探測(cè)［16］來(lái)獲得該節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的下一跳信息，然后在利用選擇函數(shù)來(lái)選擇更優(yōu)化合理的下一跳節(jié)點(diǎn)。IN進(jìn)行路徑探測(cè)所獲得鄰居節(jié)點(diǎn)的信息可能出現(xiàn)四種情況，下面對(duì)這四種情況分別討論如下:

(1)如果鄰居節(jié)點(diǎn)中包含匯聚節(jié)點(diǎn)(如圖3中虛線區(qū)域所示)，則不進(jìn)行選擇函數(shù)計(jì)算，把匯聚節(jié)點(diǎn)作為該節(jié)點(diǎn)發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)的下一跳節(jié)點(diǎn)。因?yàn)閿?shù)據(jù)直接傳送給匯聚節(jié)點(diǎn)能減少給其他節(jié)點(diǎn)帶來(lái)的負(fù)擔(dān)及整個(gè)網(wǎng)絡(luò)的能量消耗。

圖3 IN的鄰居節(jié)點(diǎn)包含Sink節(jié)點(diǎn)

(2)如果鄰居節(jié)點(diǎn)中既包含骨干節(jié)點(diǎn)又包含獨(dú)立節(jié)點(diǎn)(如圖4虛線區(qū)域所示)，則對(duì)獨(dú)立節(jié)點(diǎn)不予考慮，只考慮骨干節(jié)點(diǎn)，如果有幾個(gè)骨干節(jié)點(diǎn)處于同一條路徑上，則只保留到達(dá)匯聚節(jié)點(diǎn)跳數(shù)最少的骨干節(jié)點(diǎn)，放棄其他節(jié)點(diǎn)。最后選擇的節(jié)點(diǎn)都是各條通往匯聚節(jié)點(diǎn)路徑上距匯聚節(jié)點(diǎn)跳數(shù)最少的骨干節(jié)點(diǎn)，用Nj表示。

圖4 IN的鄰居節(jié)點(diǎn)包含兩類節(jié)點(diǎn)

定義4選擇函數(shù)P與PAj成正比，與dij和Hj成反比。即獨(dú)立節(jié)點(diǎn)INi選擇下一跳節(jié)點(diǎn)的函數(shù)為:

其中，PAj為Nj所在路徑上的最小可用能量，dij為節(jié)點(diǎn)INi和Nj的直接通信距離，Hj為骨干節(jié)點(diǎn)Nj到匯聚節(jié)點(diǎn)的跳數(shù)。

該IN可以根據(jù)選擇每個(gè)骨干節(jié)點(diǎn)的函數(shù)值和每項(xiàng)的通信代價(jià)［17］計(jì)算本身到匯聚節(jié)點(diǎn)的代價(jià)COST(INj)，該代價(jià)可用于其他獨(dú)立節(jié)點(diǎn)選擇下一跳節(jié)點(diǎn)時(shí)的函數(shù)計(jì)算。由于網(wǎng)絡(luò)中骨干路由樹的覆蓋度較高，因此僅對(duì)這些經(jīng)過(guò)一跳到達(dá)骨干路由樹的獨(dú)立節(jié)點(diǎn)進(jìn)行特殊考慮，其他經(jīng)過(guò)多跳到達(dá)骨干路由樹的節(jié)點(diǎn)不予考慮。

定義5獨(dú)立節(jié)點(diǎn)INj的代價(jià)為各個(gè)下一跳節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)通信代價(jià)的平均值，即

其中，PAj為最小可用能量，dij為直接通信距離，Hj為骨干節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù)。

(3)如果鄰居節(jié)點(diǎn)全部是獨(dú)立節(jié)點(diǎn)(如圖5虛線區(qū)域所示)，并且這些獨(dú)立節(jié)點(diǎn)中含有經(jīng)過(guò)一跳就可到達(dá)骨干路由樹的節(jié)點(diǎn)，則只對(duì)這部分節(jié)點(diǎn)(用INj表示)進(jìn)行考慮，放棄其余獨(dú)立節(jié)點(diǎn)。這樣可以使數(shù)據(jù)盡快到達(dá)匯聚節(jié)點(diǎn)并減少整個(gè)網(wǎng)絡(luò)的能量消耗。

定義6選擇函數(shù)P與Rj成正比，與dij和Cost(Nj)成反比。即INi的選擇函數(shù)為:

其中，Rj為獨(dú)立節(jié)點(diǎn)INj的剩余能量，dij為節(jié)點(diǎn)INi和INj的直接通信距離，Cost(Nj)為獨(dú)立節(jié)點(diǎn)INj到匯聚節(jié)點(diǎn)的代價(jià)。

圖5 含一跳到達(dá)骨干節(jié)點(diǎn)的節(jié)點(diǎn)

(4)如果鄰居節(jié)點(diǎn)全部是獨(dú)立節(jié)點(diǎn)(如圖6虛線區(qū)域所示)，并且這些獨(dú)立節(jié)點(diǎn)都不能經(jīng)過(guò)一跳到達(dá)骨干路由樹，則根據(jù)獨(dú)立節(jié)點(diǎn)INi到獨(dú)立節(jié)點(diǎn)INj的直接通信距離dij以及獨(dú)立節(jié)點(diǎn)INj的剩余能量Rj進(jìn)行選擇函數(shù)計(jì)算。

定義7獨(dú)立節(jié)點(diǎn)INi的代價(jià)選擇函數(shù)為:

其中，RNj為獨(dú)立節(jié)點(diǎn)INj的剩余能量，dij為直接通信距離，考慮上述決策值在數(shù)量級(jí)上可能不一致，需要進(jìn)行歸一化，dmax和Rmax分別為到所有鄰居節(jié)點(diǎn)距離的最大值和剩余能量的最大值;t為權(quán)重系數(shù)。

圖6 不含一跳到達(dá)骨干節(jié)點(diǎn)的節(jié)點(diǎn)

由上述可以看出，鄰居節(jié)點(diǎn)距離獨(dú)立節(jié)點(diǎn)越近，剩余能量越多，其代價(jià)函數(shù)值越小，從而被選擇為路由節(jié)點(diǎn)。該路由選擇策略具有良好的方向性和節(jié)點(diǎn)能量均衡性［18］。從而使基于節(jié)點(diǎn)剩余能量進(jìn)行數(shù)據(jù)傳輸?shù)穆酚芍?，能量較多的節(jié)點(diǎn)得到充分利用，保護(hù)能量較少的節(jié)點(diǎn)。

2.3.2 選擇函數(shù)的自適應(yīng)調(diào)整策略

針對(duì)2.3.1節(jié)中第4種情況可能會(huì)出現(xiàn)“折線效應(yīng)”，對(duì)選擇函數(shù)中的權(quán)重系數(shù)t引入自適應(yīng)調(diào)整機(jī)制，其計(jì)算公式為:

其中，n0為網(wǎng)絡(luò)第1次建立數(shù)據(jù)路由的節(jié)點(diǎn)跳數(shù);k為“折線效應(yīng)”判定系數(shù)，可取≥1的整數(shù);h為某次數(shù)據(jù)路由的當(dāng)前跳數(shù)。當(dāng)h≥kn0時(shí)，判定為出現(xiàn)“折線效應(yīng)”。

在網(wǎng)絡(luò)運(yùn)行初期，路由尚未出現(xiàn)“折線效應(yīng)”時(shí)，權(quán)重系數(shù)t=t0;而當(dāng)h≥kn0時(shí)，出現(xiàn)“折線效應(yīng)”，權(quán)重系數(shù)t的值以指數(shù)形式增加，如圖7所示，增加了距離因子在選擇函數(shù)P中的重要程度，從而剩余能量較多的節(jié)點(diǎn)對(duì)路由的吸引力降低，路由的方向性得以改善，“折線效應(yīng)”開始被抑制;在路由跳數(shù)持續(xù)增大的情況下，權(quán)重系數(shù)t會(huì)繼續(xù)增加并趨于1，逐漸降低“折線效應(yīng)”。當(dāng)t=1時(shí)，路由協(xié)議即退化為純地理信息路由?！罢劬€效應(yīng)”的消除可以減小路由的延時(shí)，降低網(wǎng)絡(luò)總能耗。

圖7 權(quán)重系數(shù)的變化

3 實(shí)驗(yàn)仿真

為了評(píng)估本文路由算法的性能，在NS2中分別把GEAR和本文算法進(jìn)行了仿真。重點(diǎn)通過(guò)網(wǎng)絡(luò)的吞吐量、死亡節(jié)點(diǎn)數(shù)以及端到端延遲來(lái)進(jìn)行對(duì)比分析，仿真結(jié)果表明，CEAR算法能夠達(dá)到預(yù)期效果。

在仿真環(huán)境中，設(shè)置網(wǎng)絡(luò)范圍為150 m×150 m，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100并隨機(jī)分布，匯聚節(jié)點(diǎn)處于整個(gè)網(wǎng)絡(luò)的幾何中心。仿真中采用NS2提供的CMU無(wú)線模塊，該模塊實(shí)現(xiàn)了傳輸帶寬為1 M的802.11協(xié)議，Sink節(jié)點(diǎn)的初始能量設(shè)置為10 J，發(fā)送功率為0.5 W，接收功率為 0.4 W，節(jié)點(diǎn)的通信距離為40 m，傳感器節(jié)點(diǎn)的初始能量在1 J～6 J間隨機(jī)分布。數(shù)據(jù)包大小為4 000 bit，發(fā)送的時(shí)間間隔為0.5 s，網(wǎng)絡(luò)運(yùn)行時(shí)間為 40 s。網(wǎng)絡(luò)參數(shù)k=1、t0=0.5。使用gawk腳本對(duì)生成的.tr文件進(jìn)行分析，仿真實(shí)驗(yàn)結(jié)果如圖8、9、10、11 所示。

圖8顯示了網(wǎng)絡(luò)在相同的時(shí)間內(nèi)發(fā)送的數(shù)據(jù)包數(shù)量基本相同。

圖8 發(fā)送包數(shù)目對(duì)比

圖9顯示了網(wǎng)絡(luò)中的數(shù)據(jù)包接收數(shù)量，從圖中可見，開始一段時(shí)間內(nèi)，GEAR路由協(xié)議算法下的匯聚節(jié)點(diǎn)收到的數(shù)據(jù)包數(shù)量要略高于CEAR路由算法。當(dāng)網(wǎng)絡(luò)運(yùn)行一段時(shí)間后，CEAR算法中接收數(shù)據(jù)包的數(shù)量逐漸與GEAR路由協(xié)議算法持平，在剩余的大部分時(shí)間內(nèi)，CEAR的匯聚節(jié)點(diǎn)收包數(shù)明顯高于GEAR路由協(xié)議。因?yàn)镃EAR算法周期性的生成能量閾值保護(hù)了低能量節(jié)點(diǎn)，并且骨干節(jié)點(diǎn)和獨(dú)立節(jié)點(diǎn)有規(guī)則地控制數(shù)據(jù)傳輸，盡可能的避免了通信中斷，進(jìn)而使得數(shù)據(jù)包發(fā)送成功率得到較大程度的改善。

圖9 接收包數(shù)目對(duì)比圖

圖10顯示了網(wǎng)絡(luò)中的死亡節(jié)點(diǎn)數(shù)，從圖中可以看出，網(wǎng)絡(luò)運(yùn)行的前一段時(shí)間，CEAR算法中的死亡節(jié)點(diǎn)數(shù)要明顯低于GEAR路由協(xié)議。而網(wǎng)絡(luò)運(yùn)行后期，CEAR路由協(xié)議中死亡節(jié)點(diǎn)數(shù)與GEAR路由協(xié)議基本持平，甚至在最后階段超過(guò)了GEAR路由協(xié)議。因?yàn)镃EAR算法使用了能量閾值，隨著網(wǎng)絡(luò)的運(yùn)行，低能量節(jié)點(diǎn)會(huì)逐漸增多，所以死亡節(jié)點(diǎn)數(shù)會(huì)出現(xiàn)增多的現(xiàn)象。另外，CEAR算法Sink節(jié)點(diǎn)收包數(shù)明顯高于GEAR路由協(xié)議，表明網(wǎng)絡(luò)運(yùn)行后期，CEAR算法消耗更多的能量，導(dǎo)致死亡節(jié)點(diǎn)數(shù)目增多。這從側(cè)面反應(yīng)了CEAR算法處于正常運(yùn)行狀態(tài)的時(shí)間要長(zhǎng)于GEAR路由協(xié)議。

圖10 死亡節(jié)點(diǎn)數(shù)對(duì)比圖

圖11顯示了數(shù)據(jù)包從源節(jié)點(diǎn)到Sink節(jié)點(diǎn)的傳輸延時(shí)。從圖中可知，CEAR算法端到端的平均時(shí)延減小，隨著節(jié)點(diǎn)數(shù)增加，網(wǎng)絡(luò)中的數(shù)據(jù)流量也會(huì)增加，進(jìn)而造成延時(shí)也加大。CEAR算法通過(guò)建立骨干路由樹和對(duì)部分獨(dú)立節(jié)點(diǎn)的選擇函數(shù)引入自適應(yīng)調(diào)整策略來(lái)盡可能的抑制“折線效應(yīng)”，使源節(jié)點(diǎn)和Sink節(jié)點(diǎn)之間的路由得到優(yōu)化，數(shù)據(jù)包的平均傳輸路徑變短，從而降低了端到端的傳輸時(shí)延。

圖11 傳輸數(shù)據(jù)包延時(shí)對(duì)比圖

4 總結(jié)與展望

本文提出了一種基于能量感知的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分類控制路由算法(CEAR)。該算法根據(jù)能量閾值周期性地把普通節(jié)點(diǎn)分為骨干節(jié)點(diǎn)和獨(dú)立節(jié)點(diǎn)，從而保護(hù)低能量節(jié)點(diǎn)。骨干節(jié)點(diǎn)根據(jù)骨干路由樹生成算法建立骨干路由樹，骨干節(jié)點(diǎn)按照骨干路由樹進(jìn)行數(shù)據(jù)的傳輸，獨(dú)立節(jié)點(diǎn)根據(jù)保存的周圍鄰居節(jié)點(diǎn)信息利用能量效用選擇函數(shù)選擇下一跳節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸。對(duì)部分選擇函數(shù)引入自適應(yīng)調(diào)整策略來(lái)消除折線效應(yīng)，從而減小路由的延時(shí)，提高路由的時(shí)效性。仿真結(jié)果表明，CEAR算法克服了GEAR路由協(xié)議算法的缺陷，能夠進(jìn)一步均衡能耗，降低數(shù)據(jù)傳輸延時(shí)，延長(zhǎng)網(wǎng)絡(luò)生命周期。

目前，無(wú)線傳感器網(wǎng)絡(luò)路由算法的研究是非常廣泛的，不少新穎的想法被相繼提出。然而，大多數(shù)都還停留在理論研究階段，網(wǎng)絡(luò)環(huán)境設(shè)置相對(duì)簡(jiǎn)單，與真實(shí)的復(fù)雜場(chǎng)景相比還有很大差距。本文也只是做了一定的理論設(shè)計(jì)，算法的現(xiàn)實(shí)可行性還要進(jìn)一步驗(yàn)證。在本文的基礎(chǔ)上，有很多值得繼續(xù)研究和探討的地方:能量閾值不是通過(guò)全網(wǎng)節(jié)點(diǎn)的能量情況來(lái)計(jì)算的，如果能夠設(shè)計(jì)出更優(yōu)的公式計(jì)算出最理想的能量閾值，對(duì)于延長(zhǎng)網(wǎng)絡(luò)生命周期將會(huì)具有更加重要的意義;另外本文的仿真實(shí)驗(yàn)方案稍顯簡(jiǎn)單，要進(jìn)一步提高算法的有效性，在后續(xù)工作中，最好能夠在一些比較典型的異構(gòu)網(wǎng)絡(luò)中對(duì)算法進(jìn)行模擬實(shí)驗(yàn)。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Wireless Sensor Networks［J］.IEEE Communication Magazine，2009，40(8):102－114.

［2］于海斌，曾鵬，梁群.智能無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)［M］.北京:科學(xué)出版社，2006:215－278.

［3］李建中，高宏.無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2008，45(1):1－15.

［4］Hedetniemi S，Liestman A.A Survey of Gossiping and Broadcasting in Communication Networks［J］.Network，2002，18(4):319－349.

［5］Shah R C，Rabaey J M.Energy Aware Routing for low Energy Ad hoc Sensor Networks［C］//Proc.of the IEEE Wireless Communications and Networking Conference.New York，USA:［s.n.］，2006.

［6］Kulik J，Heinzelman W，BalakrishnanH.Negotiation Based Protocolsfor Disseminating Information in Wireless Sensor Networks［J］.Wireless Networks，2009，8(2/3): － .

［7］Sun Yong，lingBo，ZhangZonglin.EnergyEfficientNode Placement Method of Wireless Sensor Networks Based on Uneven Ring Belt Model［J］.Chinese Journal of Sensors and Actuators，2008，19(4):1287－1289.

［8］YOUNIS O，F(xiàn)AHMY S.A Hybrid Energy Efficent Distributed Clustering Approach for Ad_Hoc sensor Networks［J］.IEEE Transcations on Mobile Computing，2004，3(4):660－66.

［9］Karlof C，Wagner D.Secure Routing in Wireless Sensor Networks:Attacks and Mountermeasures.The 1st IEEE Int’1 Workshop on Sensor Network Protocol and Applications，Anchorage，Alaska，2007.

［10］Shan R C，Mabaey J.Energy Aware Routing for Low Energy Ad Hoc Sensor Networks［C］//Wirless Communication and Networking Conf(WCNC 2002)，F(xiàn)lorida，USA，2002.

［11］Yu V，Govindan R，Estrin D.Geographical and Energy Aware Routing:a Recursive Data Dissemination Protocol for Wireless Sensor Networks［R］.http://graphics.stanford.edu/courses/cs428－03－spring/papers/reading/Networking/Estringeo－routingo1.pdf，2009－03－15.

［12］張學(xué)，陸桑璐，陳貴海.無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂疲跩］.軟件學(xué)報(bào)，2008，18(4):943－954.

［13］KIM M，JEONG E，BANG Y C，et al.Multipath Energy-Aware Routing Protocol in Wireless Sensor Networks［C］//INSS 2008:Proceedings of the 5th International Conference on Networked Sensing Systems.Kanazawa［s.n.］，2008:127－130.

［14］李翔，閻新芳，孫雨耕，等.無(wú)線傳感器網(wǎng)絡(luò)中簇樹骨干網(wǎng)的構(gòu)建及算法［J］.傳感技術(shù)學(xué)報(bào)，2006，19(4):1279－1283.

［15］郝曉辰，竇晶晶，劉浩然，等.基于鏈路質(zhì)量的WSN代價(jià)均衡路由選擇算法［J］.電子與信息學(xué)報(bào)，2010，32(5):1212－1218.

［16］Conti M，F(xiàn)rancesco M D，Passarella A，et al.Energy Conservation in Wireless Sensor Networks:A Survey［J］.Ad Hoc Networks，2009，(7):537－568.

［17］劉群，先興平，郭松濤.無(wú)線傳感器網(wǎng)絡(luò)路由中合作性重復(fù)博弈模型的研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23(9):1322－1327.

［18］黃旗明，劉笑.均衡能耗和時(shí)延的無(wú)線傳感器網(wǎng)絡(luò)組內(nèi)融合機(jī)制研究［J］.傳感技術(shù)學(xué)報(bào)，2009，22(1):126－130.