李 輝，劉書吉

?

基于節(jié)點(diǎn)度和距離的WSN分簇路由算法

李 輝，劉書吉

(河南理工大學(xué)電氣工程與自動(dòng)化學(xué)院，河南 焦作 454000)

針對(duì)無線傳感器網(wǎng)絡(luò)(WSN)中節(jié)點(diǎn)的負(fù)載均衡問題，提出一種基于節(jié)點(diǎn)度和距離的WSN非均勻分簇路由算法。該算法在首輪成簇時(shí)采用了定時(shí)機(jī)制的簇頭競(jìng)爭(zhēng)方案，定時(shí)的長(zhǎng)短取決于節(jié)點(diǎn)本身的節(jié)點(diǎn)度和距離基站的距離，且節(jié)點(diǎn)根據(jù)不同的競(jìng)爭(zhēng)半徑形成不同的簇。在首輪成簇結(jié)束后，簇的結(jié)構(gòu)不再發(fā)生變化，而簇頭的輪換則根據(jù)簇內(nèi)節(jié)點(diǎn)的剩余能量和距離本簇質(zhì)心的通信代價(jià)在簇內(nèi)進(jìn)行動(dòng)態(tài)輪換。采用簇間多跳路由，根據(jù)節(jié)點(diǎn)的剩余能量、距離基站的距離、節(jié)點(diǎn)間通信代價(jià)和節(jié)點(diǎn)的轉(zhuǎn)發(fā)熱度來選擇中繼節(jié)點(diǎn)。仿真結(jié)果表明，該算法的網(wǎng)絡(luò)生命周期與LEACH協(xié)議相比延長(zhǎng)了2倍以上，與EEUC協(xié)議相比延長(zhǎng)了13.97%，且均衡了網(wǎng)絡(luò)的能量消耗。

無線傳感器網(wǎng)絡(luò)；非均勻分簇；節(jié)點(diǎn)度；距離；轉(zhuǎn)發(fā)熱度；動(dòng)態(tài)輪換

1 概述

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)是繼互聯(lián)網(wǎng)之后的又一個(gè)對(duì)人類生活產(chǎn)生重大影響的IT技術(shù)[1]。由于傳感器節(jié)點(diǎn)的能量受限，因此基于分層的路由協(xié)議備受關(guān)注。基于概率的低功耗自適應(yīng)分簇協(xié)議(Low-energy Adaptive Clustering Hierarchy, LEACH)[2]是最早的分簇路由協(xié)議，幾乎貫穿了后來發(fā)展的大多數(shù)分簇協(xié)議。該協(xié)議通過等概率隨機(jī)循環(huán)地選擇簇頭以此來將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)上，從而達(dá)到降低網(wǎng)絡(luò)能量耗費(fèi)、延長(zhǎng)網(wǎng)絡(luò)生命周期的目的[3]。LEACH協(xié)議成簇時(shí)簇首選擇方法簡(jiǎn)單，易于實(shí)現(xiàn)。但是，LEACH協(xié)議的缺點(diǎn)也非常明顯：(1)在簇頭選擇時(shí)沒有考慮能量因素，無論節(jié)點(diǎn)的剩余能量多少都有可能成為簇頭，從而加速了低能量節(jié)點(diǎn)的死亡；(2)簇頭分布不均；(3)在數(shù)據(jù)傳輸時(shí)采用了單跳模式數(shù)據(jù)傳輸，當(dāng)傳輸相同的數(shù)據(jù)時(shí)距離基站遠(yuǎn)的簇頭的節(jié)點(diǎn)能耗較快。文獻(xiàn)[4]的HEED算法在簇頭選擇時(shí)依據(jù)主參數(shù)能量和次參數(shù)簇內(nèi)通信代價(jià)，其分簇速度更快，并且產(chǎn)生的簇頭分布比較均勻、網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也更加合理。但是在成簇時(shí)通信開銷大。文獻(xiàn)[5]提出的最小ID分簇算法，方法簡(jiǎn)單易行。但是在成簇時(shí)需要相互交換ID號(hào)，帶來很大的能量開銷，并且選擇的簇頭分布不太均勻。文獻(xiàn)[6]提出的集中式分簇算法(LEACH-C)，每輪結(jié)束時(shí)將能量信息和位置信息發(fā)送給基站，由基站來選擇簇頭。雖然解決了簇頭分布不均問題，但是每輪都要發(fā)送能量和位置信息浪費(fèi)了大量的能量。文獻(xiàn)[7]提出的基于競(jìng)爭(zhēng)的非均勻分簇算法(EEUC)中提出一種部分節(jié)點(diǎn)競(jìng)爭(zhēng)的方式來競(jìng)爭(zhēng)簇頭。但是每輪都要進(jìn)行簇頭的競(jìng)爭(zhēng)，若是參與競(jìng)爭(zhēng)的節(jié)點(diǎn)多時(shí)能量浪費(fèi)比較嚴(yán)重。文獻(xiàn)[8]提出了CEERP協(xié)議，該協(xié)議在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)利用的是代價(jià)函數(shù)。主要考慮了當(dāng)前節(jié)點(diǎn)和成為下一跳節(jié)點(diǎn)之間的距離和能量的加權(quán)值。文獻(xiàn)[9]提出的WSN中基于能量代價(jià)的能量?jī)?yōu)化路由算法在選擇平面路由時(shí)利用了節(jié)點(diǎn)間能量代價(jià)函數(shù)和前向區(qū)域來選擇下一跳節(jié)點(diǎn)。文獻(xiàn)[10]提出的能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議分簇時(shí)采用了定時(shí)機(jī)制，一定程度上減少了信息交互量。而選擇路由時(shí)采用了貪婪機(jī)制和代價(jià)函數(shù)相結(jié)合的方法選擇下一跳。然而，在選擇中繼節(jié)點(diǎn)時(shí)僅考慮鏈路代價(jià)函數(shù)，父節(jié)點(diǎn)在選擇下一跳節(jié)點(diǎn)時(shí)具有明顯的傾向性，即在滿足條件的節(jié)點(diǎn)中選擇最好的節(jié)點(diǎn)來轉(zhuǎn)發(fā)數(shù)據(jù)，而沒有考慮到節(jié)點(diǎn)間的負(fù)載均衡。文獻(xiàn)[11]提出支持負(fù)載均衡的無線傳感路由協(xié)議中為了均衡網(wǎng)絡(luò)的能量消耗，使用了“熱度聲明”的策略，通過設(shè)定閾值來實(shí)現(xiàn)。然而，采用設(shè)定閾值的策略，會(huì)造成一些有能力承擔(dān)轉(zhuǎn)發(fā)任務(wù)的節(jié)點(diǎn)，因?yàn)殚撝档脑蚨辉俪袚?dān)轉(zhuǎn)發(fā)任務(wù)。

針對(duì)上述算法不足，本文提出一種基于節(jié)點(diǎn)度和距離的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法(Unequal Clustering Routing Algorithm Based on Node Degree and Distance for WSN, UCDD)，該算法在首輪采用定時(shí)驅(qū)動(dòng)機(jī)制和競(jìng)爭(zhēng)半徑相結(jié)合實(shí)現(xiàn)非均勻分簇。簇形成后簇的結(jié)構(gòu)不變，而簇頭的輪換采用簇內(nèi)動(dòng)態(tài)輪換。在數(shù)據(jù)傳輸過程中采用了多跳數(shù)據(jù)傳輸模式，簇頭節(jié)點(diǎn)在選擇下一跳中繼節(jié)點(diǎn)時(shí)依據(jù)一種新的代價(jià)函數(shù)，新的代價(jià)函數(shù)不僅考慮了節(jié)點(diǎn)間的通信代價(jià)和節(jié)點(diǎn)的剩余能量，還考慮了簇頭的“轉(zhuǎn)發(fā)熱度”。

2 相關(guān)模型的假設(shè)

2.1 網(wǎng)絡(luò)模型的假設(shè)

在本文中，網(wǎng)絡(luò)中有個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)邊長(zhǎng)為正方形區(qū)域內(nèi)，并假設(shè)傳感器網(wǎng)絡(luò)具有如下性質(zhì)：

(1)基站部署在正方形監(jiān)測(cè)區(qū)域的外側(cè)。傳感器節(jié)點(diǎn)和基站部署后均不再發(fā)生位置變化，且基站唯一。

(2)所有的傳感器節(jié)點(diǎn)都是同構(gòu)的，并在網(wǎng)絡(luò)中的地位、作用相同，具有相同的初始能量，并且都有一個(gè)且唯一一個(gè)ID號(hào)，均具備數(shù)據(jù)融合的能力。

(3)各傳感器節(jié)點(diǎn)的能量受限，并且節(jié)點(diǎn)具有活動(dòng)和睡眠兩種狀態(tài)的切換能力。

(4)鏈路是對(duì)稱的。若已知發(fā)送方的發(fā)射功率，接收方可以根據(jù)信號(hào)的強(qiáng)度計(jì)算兩者間距離的近似值。

(5)節(jié)點(diǎn)位置可以通過定位算法或GPS等方法獲得。

(6)節(jié)點(diǎn)可根據(jù)距離的遠(yuǎn)近調(diào)節(jié)發(fā)射功率以節(jié)省能量。

2.2 網(wǎng)絡(luò)的能量模型

2.3 數(shù)據(jù)融合模型

3 UCDD算法的基本思想

本文提出的基于節(jié)點(diǎn)度和距離的無線傳感器網(wǎng)絡(luò)非均勻分簇路由算法(UCDD)在首輪成簇時(shí)采用了基于定時(shí)機(jī)制的分布式競(jìng)爭(zhēng)成簇算法，減少了在成簇時(shí)信息交互帶來的能量消耗，并且在生成定時(shí)器時(shí)充分考慮了節(jié)點(diǎn)度和節(jié)點(diǎn)距離基站的距離因素。多數(shù)分簇路由協(xié)議采用的周期性成簇機(jī)制會(huì)帶來一些不必要的能量消耗。因此，UCDD算法只在首輪進(jìn)行成簇操作，簇一旦形成將不再發(fā)生改變，在一定程度上減少了成簇帶來的能量消耗，還可以穩(wěn)定簇頭的個(gè)數(shù)。為了減少“熱區(qū)”給網(wǎng)絡(luò)帶來的影響采用了非均勻分簇的思想，使成簇大小隨著距離基站的距離的增加而增大。簇首的輪換采用簇內(nèi)動(dòng)態(tài)輪換，在輪換時(shí)簇頭節(jié)點(diǎn)根據(jù)本簇的存活節(jié)點(diǎn)的平均能量水平來決定是否選取下一任簇頭節(jié)點(diǎn)，并充分考慮了下一任節(jié)點(diǎn)的能量水平和距離本簇質(zhì)心的通信代價(jià)。在穩(wěn)定的數(shù)據(jù)傳輸階段，簇頭通過多跳的方式將本簇的數(shù)據(jù)傳給基站，在建立路由時(shí)提出一種合理選擇下一跳的代價(jià)函數(shù)，不僅考慮了節(jié)點(diǎn)間的通信代價(jià)和節(jié)點(diǎn)的剩余能量，還考慮了簇頭的“轉(zhuǎn)發(fā)熱度”。在多跳傳輸過程中，節(jié)點(diǎn)通過計(jì)算滿足條件的簇頭的代價(jià)函數(shù)，選擇代價(jià)最小的簇頭作為下一跳進(jìn)行數(shù)據(jù)的傳輸。由于在選擇下一跳節(jié)點(diǎn)時(shí)考慮了簇頭的“轉(zhuǎn)發(fā)熱度”，在一定程度上均衡了鏈路之間的能耗，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。圖1為UCDD算法的原理，圖中大小圓圈代表簇和簇頭，五邊形是基站，帶箭頭的線表示簇間路由[10]。

圖1 UCDD算法原理

3.1 簇的形成

UCDD算法的一種完全分布式的競(jìng)爭(zhēng)成簇算法，最終目標(biāo)是實(shí)現(xiàn)非均勻分簇。當(dāng)節(jié)點(diǎn)部署結(jié)束后，節(jié)點(diǎn)通過廣播交換信息來統(tǒng)計(jì)節(jié)點(diǎn)度信息，根據(jù)接收的基站的廣播信號(hào)強(qiáng)度計(jì)算距離基站的距離。節(jié)點(diǎn)信息表見表1。

表1 節(jié)點(diǎn)信息表

節(jié)點(diǎn)的競(jìng)爭(zhēng)規(guī)則如下：

規(guī)則在競(jìng)爭(zhēng)過程中，節(jié)點(diǎn)一旦競(jìng)爭(zhēng)勝利，將在自己的競(jìng)爭(zhēng)半徑內(nèi)廣播成為簇頭的消息，在其競(jìng)爭(zhēng)半徑內(nèi)的節(jié)點(diǎn)將不再參與競(jìng)爭(zhēng)，進(jìn)入休眠狀態(tài)直到競(jìng)爭(zhēng)結(jié)束。否則繼續(xù)競(jìng)爭(zhēng)。

本文的算法借鑒了EEUC算法中競(jìng)爭(zhēng)半徑的計(jì)算方法，節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑公式如下：

本文算法在簇頭競(jìng)爭(zhēng)階段采用定時(shí)廣播代替了協(xié)商機(jī)制。傳統(tǒng)的算法如EEUC在簇頭競(jìng)爭(zhēng)過程中節(jié)點(diǎn)的剩余能量大于所有的候選簇頭時(shí)競(jìng)選才成功，并且要廣播通知信息和接收其他候選簇頭的放棄競(jìng)爭(zhēng)的廣播信息。如果節(jié)點(diǎn)密度較大時(shí)每個(gè)候選簇頭都要接收和廣播大量信息，浪費(fèi)很多能量。若采用定時(shí)驅(qū)動(dòng)機(jī)制在一定程度上減少算法的迭代次數(shù)和信息交互帶來的能量消耗。本文定時(shí)公式如下：

其中，是均勻分布在之間的隨機(jī)數(shù)，用于減小廣播消息時(shí)間沖突的可能性；為設(shè)定的簇頭最大競(jìng)爭(zhēng)時(shí)間；為節(jié)點(diǎn)的節(jié)點(diǎn)度；是網(wǎng)絡(luò)中布撒的節(jié)點(diǎn)個(gè)數(shù)；是節(jié)點(diǎn)與基站之間的距離；是網(wǎng)絡(luò)中節(jié)點(diǎn)到基站的最大距離。由式(7)可知，節(jié)點(diǎn)度越高，距離基站的距離越小，生成的定時(shí)時(shí)間就越短，成為最終簇的概率就越大。簇的形成流程見圖2。在成簇時(shí)，節(jié)點(diǎn)根據(jù)接收到簇首的信號(hào)強(qiáng)度選擇信號(hào)強(qiáng)度最大的加入，若節(jié)點(diǎn)接收的簇頭的信號(hào)強(qiáng)度相同，選擇簇頭節(jié)點(diǎn)度低的簇頭加入。成簇結(jié)束后簇頭節(jié)點(diǎn)為每個(gè)簇成員分配一個(gè)TMDA時(shí)隙，簇內(nèi)節(jié)點(diǎn)根據(jù)分配的時(shí)隙與各自的簇頭進(jìn)行通信。

3.2 簇間路由的建立

UCDD算法采用了簇內(nèi)單跳和簇間多跳的方式進(jìn)行數(shù)據(jù)的傳輸。簇頭節(jié)點(diǎn)只是在其鄰居簇首集合中選擇一個(gè)合適的簇頭中繼來轉(zhuǎn)發(fā)數(shù)據(jù)到基站。和PEGASIS算法[13]不同，UCDD算法中的中繼簇頭只是簡(jiǎn)單的轉(zhuǎn)發(fā)并不融合轉(zhuǎn)發(fā)的數(shù)據(jù)。

定義3轉(zhuǎn)發(fā)熱度就是利用該簇頭作為中繼節(jié)點(diǎn)的所有子簇頭的個(gè)數(shù)，簇頭初始轉(zhuǎn)發(fā)熱度為0。

在建立簇間路由時(shí)，每個(gè)簇首節(jié)點(diǎn)以3倍[10]于自身競(jìng)爭(zhēng)半徑進(jìn)行廣播簇間通信信息。并且路由的發(fā)起從最遠(yuǎn)端發(fā)起，簇頭節(jié)點(diǎn)根據(jù)距離基站的距離依次建立路由。簇頭節(jié)點(diǎn)廣播信息包括簇頭的ID、簇首與基站之間的距離、簇頭剩余能量，簇首節(jié)點(diǎn)通過接收的簇頭廣播信息計(jì)算相互間的距離。簇頭節(jié)點(diǎn)根據(jù)收到的廣播信息，建立鄰居簇首集合。鄰居簇頭集合分為子節(jié)點(diǎn)集合和父節(jié)點(diǎn)集合。

3.3 簇頭的輪換機(jī)制

(14)

由式(11)可知，在進(jìn)行簇頭輪換時(shí)利用節(jié)點(diǎn)的剩余能量和距離簇質(zhì)心的距離來選擇下一任簇頭，使得越靠近質(zhì)心能量越高的節(jié)點(diǎn)當(dāng)選簇頭權(quán)值就越大。當(dāng)簇頭靠近質(zhì)心時(shí)，簇內(nèi)節(jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)簇內(nèi)消耗的能量就越少，降低了簇內(nèi)能量消耗，在一定程度上延長(zhǎng)了網(wǎng)絡(luò)的生命。簇頭輪換流程如圖3所示。

圖3 簇頭輪換流程

4 仿真與結(jié)果分析

4.1 仿真參數(shù)的設(shè)定

本文采用Matlb軟件對(duì)提出的算法進(jìn)行了驗(yàn)證，并在相同的條件下與LEACH協(xié)議和EEUC協(xié)議進(jìn)行了對(duì)比分析。相關(guān)參數(shù)設(shè)置如表2所示。

表2 網(wǎng)絡(luò)環(huán)境的參數(shù)設(shè)定

4.2 簇頭的特性

在分層的路由協(xié)議中，成簇時(shí)的簇頭個(gè)數(shù)對(duì)網(wǎng)絡(luò)的性能將產(chǎn)生很大的影響。一個(gè)好的分簇路由協(xié)議，當(dāng)網(wǎng)絡(luò)的參數(shù)一定時(shí)，產(chǎn)生的簇頭個(gè)數(shù)應(yīng)該在一定的期望范圍內(nèi)。本文對(duì)UCDD算法和LEACH協(xié)議都進(jìn)行了100次的仿真并統(tǒng)計(jì)了簇頭的分布情況，如圖4、圖5所示。從圖4可以看出，LEACH協(xié)議產(chǎn)生的簇頭個(gè)數(shù)范圍波動(dòng)比較大，其主要的原因是LEACH協(xié)議采用了等概率選擇簇頭的模型，通過隨機(jī)數(shù)和閾值來決定該節(jié)點(diǎn)是否當(dāng)選為簇頭節(jié)點(diǎn)。而UCDD協(xié)議產(chǎn)生的簇頭個(gè)數(shù)相對(duì)集中在一定的范圍之內(nèi)，產(chǎn)生的簇頭相對(duì)比較穩(wěn)定。主要原因是在簇頭選舉的時(shí)采用了節(jié)點(diǎn)度和局部競(jìng)爭(zhēng)相結(jié)合的方式，在一定程度上控制了產(chǎn)生的簇頭數(shù)量。從整體上來看，UCDD算法產(chǎn)生的簇頭個(gè)數(shù)相對(duì)穩(wěn)定，可靠性較好。

圖4 LEACH算法簇頭數(shù)量分布

圖5 UCDD算法簇頭數(shù)量分布

在分簇的路由協(xié)議中，由于簇頭的特殊位置，簇頭消耗的能量占據(jù)了網(wǎng)絡(luò)能耗的主要部分，因此本文對(duì)比了 3種協(xié)議簇首在一輪中所消耗的總能量。本文隨機(jī)選取了10輪，統(tǒng)計(jì)了每輪中所有簇頭消耗的能量，如圖6所示。本文UCDD算法和EEUC算法消耗的能量較小，主要的原因是在進(jìn)行數(shù)據(jù)傳輸時(shí)采用了多跳通信的方式，節(jié)約了能量消耗。而LEACH協(xié)議每輪簇首消耗的能量明顯多于UCDD算法和EEUC算法，不僅因?yàn)長(zhǎng)EACH協(xié)議是在進(jìn)行數(shù)據(jù)傳輸時(shí)采用了單跳進(jìn)行傳輸，還有LEACH協(xié)議產(chǎn)生的簇頭個(gè)數(shù)也比較多，增加了與基站通信的次數(shù)，從而增加了能量消耗。另外，LEACH協(xié)議在進(jìn)行簇頭選舉時(shí)沒有控制簇頭在網(wǎng)絡(luò)中的分布，而且簇頭的數(shù)量也不確定，因此每輪簇首消耗的能量之和有較大的波動(dòng)。UCDD協(xié)議在一定程度上克服了LEACH協(xié)議的不足，降低了網(wǎng)絡(luò)的能量消耗。

圖6 簇頭的每輪能耗之和

4.3 能量效率

對(duì)網(wǎng)絡(luò)的能量效率的證明中，網(wǎng)絡(luò)的生命周期是一個(gè)重要指標(biāo)。本文首先對(duì)比了3種協(xié)議的網(wǎng)絡(luò)生命周期。然而，網(wǎng)絡(luò)的生命周期目前也沒有統(tǒng)一的定論，有的以第一個(gè)節(jié)點(diǎn)死亡的時(shí)間作為網(wǎng)絡(luò)的生命周期(FND)，有的以一半節(jié)點(diǎn)死亡的時(shí)間作為網(wǎng)絡(luò)生命周期(HND)，還有以最后一個(gè)節(jié)點(diǎn)死亡作為網(wǎng)絡(luò)生命周期的(LND)[14]。

從圖7和圖8可以看出，3種協(xié)議中網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)隨著仿真時(shí)間的變化逐步減少。顯然，首個(gè)節(jié)點(diǎn)死亡的時(shí)間、半數(shù)節(jié)點(diǎn)死亡的時(shí)間、最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間，UCDD協(xié)議均優(yōu)于EEUC協(xié)議。只有最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間UCDD協(xié)議略微低于LEACH協(xié)議。從第一個(gè)節(jié)點(diǎn)開始死亡到最后一個(gè)節(jié)點(diǎn)死亡的時(shí)間可以反映出網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況，跨度越短說明網(wǎng)絡(luò)的能量使用越高效。UCDD協(xié)議不僅在一定程度上延長(zhǎng)網(wǎng)絡(luò)的生命周期，而且時(shí)間跨度也遠(yuǎn)小于LEACH協(xié)議，略小于EEUC協(xié)議。說明UCDD協(xié)議很好地均衡了網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗。LEACH協(xié)議在進(jìn)行簇頭選擇時(shí)采用了等概率模型，沒有考慮節(jié)點(diǎn)的剩余能量，并且在數(shù)據(jù)傳輸時(shí)采用了單跳模式，所以第一個(gè)節(jié)點(diǎn)死亡較早。EEUC協(xié)議雖然考慮了節(jié)點(diǎn)的剩余能量，但是在進(jìn)行簇頭選擇時(shí)采用部分節(jié)點(diǎn)競(jìng)爭(zhēng)機(jī)制，由于每輪都要進(jìn)行簇頭的選舉消耗了部分能量，并且在進(jìn)行數(shù)據(jù)傳輸時(shí)只考慮了下一跳節(jié)點(diǎn)的剩余能量和距離，這樣會(huì)出現(xiàn)多個(gè)節(jié)點(diǎn)選擇一個(gè)簇首作為中繼的現(xiàn)象，會(huì)造成能耗均衡性降低。如果以第一個(gè)節(jié)點(diǎn)死亡的時(shí)間進(jìn)行對(duì)比，LEACH協(xié)議出現(xiàn)首個(gè)節(jié)點(diǎn)死亡的輪數(shù)是268輪，EEUC協(xié)議出現(xiàn)的首個(gè)節(jié)點(diǎn)死亡的輪數(shù)是766輪，而UCDD協(xié)議是873輪。

本文提出的協(xié)議在生命周期方面比LEACH協(xié)議提高了2倍多，比EEUC協(xié)議提高了13.97%。

圖7 節(jié)點(diǎn)存活個(gè)數(shù)與輪數(shù)之間的關(guān)系

圖8 網(wǎng)絡(luò)的存活時(shí)間

圖9對(duì)比了網(wǎng)絡(luò)的整體能耗變化的趨勢(shì)，曲線的坡度越小代表著較慢的能耗速度和較長(zhǎng)的網(wǎng)絡(luò)生命周期。從圖中可以看出，UCDD協(xié)議的坡度要小于EEUC協(xié)議和LEACH協(xié)議。當(dāng)網(wǎng)絡(luò)都運(yùn)行到500輪時(shí)，LEACH協(xié)議消耗了161.12 J，而EEUC協(xié)議消耗了119.15 J，而UCDD算法只消耗了108.9 J，比LEACH協(xié)議提高32.4%，比EEUC提高8.6%。

圖9 網(wǎng)絡(luò)的總能耗與輪數(shù)之間的關(guān)系

5 結(jié)束語

本文在對(duì)現(xiàn)有路由協(xié)議研究的基礎(chǔ)上，針對(duì)周期性成簇、周期性選舉簇頭和利用代價(jià)函數(shù)，建立路由時(shí)容易出現(xiàn)多個(gè)節(jié)點(diǎn)同時(shí)選擇一個(gè)節(jié)點(diǎn)作為中繼的問題，從簇頭選舉、簇頭的動(dòng)態(tài)輪換和簇間路由的建立3個(gè)方面進(jìn)行了改進(jìn)，UCDD算法不僅充分利用了節(jié)點(diǎn)的能量，而且緩解了“熱區(qū)”對(duì)網(wǎng)絡(luò)的影響。仿真實(shí)驗(yàn)表明，該算法能更好地均衡網(wǎng)絡(luò)的能量消耗，有效延長(zhǎng)網(wǎng)絡(luò)的生命周期。下一步將以網(wǎng)絡(luò)編碼為基礎(chǔ)對(duì)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)進(jìn)行編碼，以此減少數(shù)據(jù)的發(fā)送量，降低節(jié)點(diǎn)的能耗。

[1] 景 博, 張 劼, 孫 勇. 智能網(wǎng)絡(luò)傳感器與無線傳感器網(wǎng)絡(luò)[M]. 北京: 國(guó)防工業(yè)出版社, 2011.

[2] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy- Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Hawaii International Conference on System Sciences. Cambridge, USA: IEEE Press, 2000: 8020-8030.

[3] 沈 波, 張世永, 鐘亦平. 無線傳感器網(wǎng)絡(luò)分簇路由協(xié) 議[J]. 軟件學(xué)報(bào), 2006, 17(7): 1588-1600.

[4] Younis O, Fahmy S. HEED: A Hybrid Energy-efficient Distri- buted Clustering Approach for Ad-hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366- 379.

[5] Lin C H R, Gerla M. A Distributed Architecture for Multi-

media in Dynamic Wireless Networks[C]//Proc. of IEEE GLOBECOM’95. Los Angeles, USA: [s. n.], 1995: 1468- 1472.

[6] Heinzelman W R, Chandrakasan A P, Balakrishnan H. An Application-specific Protocol Architectures for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-669.

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

[8] 劉星成, 袁東升. 基于代價(jià)函數(shù)的WSN能效路由協(xié)議性能分析[J]. 軟件學(xué)報(bào), 2011, 32(6): 133-140.

[9] 江海峰, 錢建生. WSN中基于能量代價(jià)的能量?jī)?yōu)化路由算法[J]. 計(jì)算機(jī)科學(xué), 2012, 39(1): 73-76.

[10] 蔣暢江, 石為人. 能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J]. 軟件學(xué)報(bào), 2012, 23(5): 1222-1232.

[11] 尹 安, 汪秉文. MintRoute-HNLB: 一種支持負(fù)載均衡的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計(jì)算機(jī)科學(xué), 2010, 37(5): 77-80.

[12] 李成岳, 申鉉京. 無線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進(jìn)[J]. 傳感技術(shù)學(xué)報(bào), 2010, 23(8): 1164-1167.

[13] Lindsey S, Raghavendra C S. PEGASIS: Power-efficient Gather in Sensor Information Systems[C]//Proc. of IEEE Aerospace Conferwnce. [S. 1.]: IEEE Press, 2002: 1125-1130.

[14] 胡 平.基于節(jié)能的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議研究[D]. 南京: 南京理工大學(xué), 2009.

編輯 索書志

Clustering Routing Algorithm Based on Node Degree and Distance for Wireless Sensor Networks

LI Hui, LIU Shu-ji

(School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo 454000, China)

Aiming at the problem of unnecessary energy consumption caused by periodic clustering and the load balance problem in the Wireless Sensor Networks(WSN), an Unequal Clustering routing algorithm based on node Degree and Distance for WSN(UCDD) is proposed. UCDD algorithm adopts the time competitive mechanism in the first round of clustering. The length of time depends on the nodes’ node degree and the distance from the base station, and different clusters are formed according to the different radius of competition. After the first round, the clusters’ structure does not change any more. Cluster head dynamically choose next cluster head according to the residual energy and the communication costs. Inter-cluster multihop routing is used in UCDD algorithm, and the relay node is selected according to node residual energy, distance from the base station, communication cost of nodes and relay hot. Simulation results show that the algorithm can prolong the networks lifetime by more than two times compared with LEACH protocol and by 13.97% compared with EEUC protocol. Besides, it balances the energy dissipation of the networks.

Wireless Sensor Networks(WSN); unequal clustering; node degree; distance; relay heat; dynamic rotation

1000-3428(2014)03-0113-07

A

TP391

李 輝(1976－)，男，副教授，主研方向：無線傳感器網(wǎng)絡(luò)；劉書吉，碩士研究生。

2013-03-04

2013-04-18 E-mail：li20042007@163.com

10.3969/j.issn.1000-3428.2014.03.023