侯愛霞

（重慶科創(chuàng)職業(yè)學(xué)院 信息與機(jī)電工程學(xué)院，重慶 402160）

基于簇的無線傳感網(wǎng)絡(luò)路由改進(jìn)算法

侯愛霞

（重慶科創(chuàng)職業(yè)學(xué)院 信息與機(jī)電工程學(xué)院，重慶 402160）

環(huán)境危害、能量耗盡、設(shè)備故障等原因常導(dǎo)致傳感節(jié)點(diǎn)錯(cuò)誤，影響無線傳感網(wǎng)絡(luò)（WSNs）的應(yīng)用性能，縮短無線傳感網(wǎng)絡(luò)壽命。為解決傳感節(jié)點(diǎn)錯(cuò)誤問題，提出面向容錯(cuò)的基于簇的分布式FTCD路由。在初始階段，傳感節(jié)點(diǎn)利用離簇頭（CH）的距離、簇頭離基站（BS）的距離及簇頭的剩余能量信息選擇自己的簇頭；在數(shù)據(jù)路由階段，簇頭以最小化能量消耗方式選擇下一跳簇頭，并提出容錯(cuò)處理。仿真實(shí)驗(yàn)結(jié)果表明，F(xiàn)TCD路由能有效應(yīng)對簇頭錯(cuò)誤，提高了能量利用率，使其多方面的性能都得到顯著提高。

WSNs；FTCD；CH；傳感節(jié)點(diǎn)

1 問題的提出

無線傳感網(wǎng)絡(luò)（W ireless Sensor Network，簡稱WSNs）被廣泛應(yīng)用于環(huán)境監(jiān)測、戰(zhàn)場勘察、健康醫(yī)療等各類行業(yè)及災(zāi)難管理[1]。目前，傳感節(jié)點(diǎn)能量的有限性及不可替換性是阻礙WSNs應(yīng)用發(fā)展的重要因素[2]，因而降低傳感節(jié)點(diǎn)能量消耗，提高能量利用率被認(rèn)為是WSNs應(yīng)用的關(guān)鍵。為此，設(shè)計(jì)有效的能量協(xié)議，包括低功耗的通信硬件、能量感知MAC協(xié)議等，其中基于能量有效的簇化路由算法被認(rèn)為是WSNs最有前景的技術(shù)[3]。

基于簇化的WSNs網(wǎng)絡(luò)模型如圖1所示。

圖1 基于簇化的WSNs網(wǎng)絡(luò)模型

傳感節(jié)點(diǎn)被劃分為不同的群，稱為簇。每個(gè)簇有一個(gè)簇頭（CH），每個(gè)傳感節(jié)點(diǎn)僅屬于一個(gè)簇[4]。簇化的WSNs有以下優(yōu)勢：一是CH接收簇內(nèi)成員的感測數(shù)據(jù)并進(jìn)行融合，摒棄冗余數(shù)據(jù)后，再向基站（BS）傳輸，降低了傳感節(jié)點(diǎn)的能量消耗。二是由CHs構(gòu)建數(shù)據(jù)傳輸主線，更容易管理路由，同時(shí)也提高了網(wǎng)絡(luò)的擴(kuò)展性和重要性。但簇化的WSNs中CH承擔(dān)了更多的任務(wù)，如從傳感節(jié)點(diǎn)接收數(shù)據(jù)并進(jìn)行融合，向基站傳輸。繁重的任務(wù)加快了CH的能量消耗，縮短了CH的工作壽命。一旦能量耗盡，CH就不能正常工作，本文將此類節(jié)點(diǎn)稱為傳感節(jié)點(diǎn)錯(cuò)誤。CH承擔(dān)了數(shù)據(jù)收集、融合、傳輸?shù)亩囗?xiàng)任務(wù)，一旦CH錯(cuò)誤，WSNs的數(shù)據(jù)傳輸將中斷，從而降低WSNs的應(yīng)用性能[5]。此外，由于環(huán)境干擾、能量耗盡及設(shè)備故障等因素，也會導(dǎo)致傳感節(jié)點(diǎn)錯(cuò)誤，影響WSNs的應(yīng)用性能，縮短WSNs工作壽命。但相較而言，CH錯(cuò)誤的危害更為嚴(yán)重。因此，為了確保WSNs的應(yīng)用性能，在設(shè)計(jì)路由協(xié)議時(shí)，必須考慮CH及傳感節(jié)點(diǎn)錯(cuò)誤，即路由具有容錯(cuò)性[6]。

基于簇化的路由算法有集中式和分布式，廣泛應(yīng)用于WSNs。集中式路由算法由BS執(zhí)行，需要掌握網(wǎng)絡(luò)拓?fù)涞娜中畔ⅲ⒙酚尚畔l(fā)送至CH；分布式路由算法依據(jù)局部信息進(jìn)行路由決策。EELBC（Energy Efficient Load-Balanced Clustering）算法強(qiáng)調(diào)能量利用率和負(fù)擔(dān)開銷的平衡[7]，但該算法是假定BS已知每個(gè)傳感節(jié)點(diǎn)和CH位置為前提。此外，這些算法并沒有考慮CH錯(cuò)誤問題。EECS（Energy-Efficient Clustering Scheme）協(xié)議在CH選擇過程中，不僅考慮了傳感節(jié)點(diǎn)的剩余能量，還考慮了離信宿的距離，提高了簇分布的均勻性[8]，但該協(xié)議并沒有考慮傳感節(jié)點(diǎn)能量消耗速率情況。DEBR（Distributed Energy Balance Routing）路由平衡網(wǎng)絡(luò)的能量消耗，但該路由沒有考慮CH錯(cuò)誤問題。MHRM（M inimum Hop Routing Model）每個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)以最短的通信跳數(shù)建立離BS的路徑，因而轉(zhuǎn)發(fā)節(jié)點(diǎn)總是選擇離自己遠(yuǎn)的一跳鄰居節(jié)點(diǎn)作為下一跳的轉(zhuǎn)發(fā)節(jié)點(diǎn)，這將消耗大量的能量[9]。FTCA（Fault Tolerant Clustering Algorithm）算法考慮CH錯(cuò)誤問題，但其路由性能差，并沒有考慮傳感節(jié)點(diǎn)的能量消耗問題。

本文提出FTCD（Fault Tolerant Clustering-based Distributed）路由，重點(diǎn)考慮CH錯(cuò)誤，分為初始階段和數(shù)據(jù)處理階段。初始階段進(jìn)行網(wǎng)絡(luò)簇化，每個(gè)傳感節(jié)點(diǎn)依據(jù)增益函數(shù)為自己選擇一個(gè)CH，增益函數(shù)融合了離CH的距離、CH的剩余能量及CH離BS的距離信息；數(shù)據(jù)處理階段，CH以平衡能量消耗的角度選擇下一跳CH，通過這種分布式路由向BS傳輸數(shù)據(jù)。

2 系統(tǒng)模型及定義

考慮N個(gè)傳感節(jié)點(diǎn)Si, i=1, 2, …, N，隨機(jī)分布于WSNs。有m個(gè)chk, k=1, 2, …, m。一旦部署后，傳感節(jié)點(diǎn)不再移動，即傳感節(jié)點(diǎn)是靜態(tài)的。為了后續(xù)描述簡單，定義以下變量：

（1）傳感節(jié)點(diǎn)集S={s1, s2, …, sN}。

（2）CH集C={ch1, ch2, …, chm}。

（3）CH的最大通信范圍Rch，傳感節(jié)點(diǎn)的通信范圍Rs。

（4）傳感節(jié)點(diǎn)si與sj間的距離d (si, sj)。

（5）傳感節(jié)點(diǎn)si的剩余能量EResidual(si)。

（6）傳感節(jié)點(diǎn)si覆蓋的CH集ComCH (si)：在傳感節(jié)點(diǎn)si的通信范圍內(nèi)所有的CH，即：

（7）傳感節(jié)點(diǎn)si的鄰居集Nei(si)：在傳感節(jié)點(diǎn)si的通信范圍內(nèi)所有的傳感節(jié)點(diǎn)，即：

（8）chk的鄰居集Com(chk)：在chk的通信范圍內(nèi)所有的CH，即：

（9）chk離BS的跳數(shù)HCou(chk)：如果chk能與BS直接通信，則HCou(chk)=1。

（10）chk后向Bch(chk)：在chk通信范圍內(nèi)，并且離BS的跳數(shù)大于chk離BS的跳數(shù)，則：

（11）被CH覆蓋的傳感節(jié)點(diǎn)集CO：若在傳感節(jié)點(diǎn)si的通信范圍內(nèi)，至少存在一個(gè)CH，那么si屬于傳感節(jié)點(diǎn)集CO；若在傳感節(jié)點(diǎn)si的通信范圍內(nèi)，不存在CH，那么si屬于非傳感節(jié)點(diǎn)集UnCO，則：

（12）非傳感節(jié)點(diǎn)集內(nèi)的傳感節(jié)點(diǎn)si的支持節(jié)點(diǎn)集Baup (si)：當(dāng)si∈UnCO，si的鄰居節(jié)點(diǎn)可作為連接CH的中間節(jié)點(diǎn)。這些中間節(jié)點(diǎn)集稱為si的支持節(jié)點(diǎn)集Baup (si)，即：

（13）活動節(jié)點(diǎn)和失效節(jié)點(diǎn)：有能量將感測數(shù)據(jù)以直接或間接方式傳輸至CH，稱為活動節(jié)點(diǎn)；將不能與CH通信的節(jié)點(diǎn)稱為失效節(jié)點(diǎn)[10]。

3 FTCD協(xié)議

BS, CH及傳感節(jié)點(diǎn)是FTCD協(xié)議內(nèi)的三個(gè)通信實(shí)體。BS周期地廣播HELLO消息，通過接收信號強(qiáng)度判斷CH離BS的距離。FTCD協(xié)議主要分為初始階段和數(shù)據(jù)處理階段。初始階段形成不同的簇；數(shù)據(jù)處理階段主要進(jìn)行數(shù)據(jù)感測、傳輸。將數(shù)據(jù)處理階段劃分為多個(gè)固定時(shí)隙回合（Round），在每一個(gè)回合中，CH接收簇成員感測的數(shù)據(jù)并進(jìn)行融合，再利用分布式路由算法傳輸至BS，如圖2所示。

圖2 FTCD協(xié)議網(wǎng)絡(luò)模型

3.1 初始階段

在初始階段，CH周期地向鄰居區(qū)域廣播HELLO消息，包含CH的ID、剩余能量及離BS的距離信息。若傳感節(jié)點(diǎn)si能收到HELLO消息，則可能收到多條HELLO消息，只要能收到1條HELLO消息，則表明傳感節(jié)點(diǎn)si至少被一個(gè)CH所覆蓋，即si∈CO；若在規(guī)定的一段時(shí)間內(nèi)沒有收到HELLO消息，則表明傳感節(jié)點(diǎn)si未被任何一個(gè)CH覆蓋，即si∈UnCO。

（1）若si∈CO，si可能收到多條HELLO消息，表明si在多個(gè)CH覆蓋區(qū)域內(nèi)。在這種環(huán)境下，si必須選擇一個(gè)CH作為它的領(lǐng)導(dǎo)者。在選擇過程中，需要考慮CH的剩余能量、離CH的距離及CH離BS的距離信息，融合為一個(gè)指標(biāo)CHco (si, chr)，即：

其中，si選擇chr作為CH的增益值，且chr∈ComCH (si)。

再從中擇優(yōu)選擇具有最大增益值的CH，即：

一旦選擇了CH，就向其發(fā)送JOIN_REQ消息；收到消息后，CH將該傳感節(jié)點(diǎn)作為自己的成員。

（2）若si∈UnCO，si未被任何一個(gè)CH覆蓋。在這種環(huán)境下，si廣播HELLO消息尋求支持，si便從Baup (si)（見（6）式）集中找到一個(gè)節(jié)點(diǎn)作為連接CH的中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。若Baup (si)≠φ，就從中選擇一個(gè)傳感節(jié)點(diǎn)作為連接CH的中間節(jié)點(diǎn)。在選擇過程中，著重考慮傳感節(jié)點(diǎn)的能量，即選擇剩余能量最大的節(jié)點(diǎn)，即：

依據(jù)上述分析，初始階段中簇的形成算法流程如圖3所示。

圖3 簇的形成算法流程

3.2 數(shù)據(jù)處理階段

CH構(gòu)成網(wǎng)絡(luò)傳輸主線，在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，充分考慮CH的能量、距離及離BS的跳數(shù)信息。為此，建立增益函數(shù)Cost (chi, chk)，表示chi選擇chk作為下一跳的增益，即：

chi選擇具有最大增益及離BS的跳數(shù)更小的CH作為下一跳的轉(zhuǎn)發(fā)節(jié)點(diǎn)，即：

3.3 容錯(cuò)性分析

在數(shù)據(jù)處理階段，由于能量耗盡等原因，CH可能失效。一旦檢測到失效的CH，該CH的成員節(jié)點(diǎn)就廣播HELP消息。假定傳感節(jié)點(diǎn)si廣播HELP消息，來自chk內(nèi)的成員節(jié)點(diǎn)sj接收此消息，且chk∈ComCH(si)，sj∈Nei (si)，并回復(fù)RELP消息。若傳感節(jié)點(diǎn)si收到來自sj發(fā)送的RELP消息，則si∈CO，并更新Baup (si)，否則si∈UnCO。容錯(cuò)處理算法流程如圖4所示。

圖4 容錯(cuò)處理算法流程

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

利用MATLAB R2012b建立仿真平臺。在400m× 400m的方形區(qū)域，BS位于區(qū)域中心（200m×200m），其中，傳感節(jié)點(diǎn)N=400，CH中m=40。每個(gè)傳感節(jié)點(diǎn)的初始能量為2J，通信半徑Rs=60m；CH的初始能量為10J，通信半徑Rch=100m。每次實(shí)驗(yàn)重復(fù)100次，取平均值作為最終數(shù)據(jù)。為了更充分地分析路由性能，選擇容錯(cuò)簇算法FTCA和分布式算法DEBR和MHRM進(jìn)行仿真實(shí)驗(yàn)比較，結(jié)果如圖5～圖7所示。

4.1 錯(cuò)誤的CH數(shù)及BS接收的數(shù)據(jù)包

由圖5可知，在整個(gè)網(wǎng)絡(luò)有效期內(nèi)，F(xiàn)TCD路由錯(cuò)誤的CH數(shù)少于DEBR, FTCA, MHRM路由的CH數(shù)。在FTCA路由中，CH直接與BS直接通信頻繁，導(dǎo)致能量消耗過快。在DERB路由中，為了平衡CH能量消耗，可能選擇與BS反方向的CH作為轉(zhuǎn)發(fā)數(shù)據(jù)的CH，可能使數(shù)據(jù)最終不能傳輸?shù)紹S，浪費(fèi)了能量。在MHRM路由中，為了限制跳數(shù)，離BS最遠(yuǎn)的CH作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，致使CH因長距離傳輸而能量消耗過快。在FTCD路由中，在選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)融合了能量、距離信息，并且具有容錯(cuò)性，一旦CH錯(cuò)誤，F(xiàn)TCD路由能尋找另一個(gè)CH進(jìn)行數(shù)據(jù)傳輸。FTCD路由的BS可接收更多的數(shù)據(jù)包，優(yōu)于DEBR, FTCA, MHRM路由，由此進(jìn)一步驗(yàn)證了FTCD路由性能的優(yōu)越性。

4.2 總體能量消耗和平均能量消耗

由圖6可知，盡管四個(gè)路由的總體能量消耗曲線走勢相同，但提出的FTCD路由略優(yōu)于DEBR, FTCA, MHRM，但隨著Round的增加，優(yōu)勢減弱。究其原因在于FTCD路由中BS接收了更多的數(shù)據(jù)包。

4.3 CH剩余能量的標(biāo)準(zhǔn)偏差和錯(cuò)誤的傳感節(jié)點(diǎn)數(shù)

圖5 錯(cuò)誤的CH數(shù)及BS接收的數(shù)據(jù)包

圖6 總體能量消耗及每接收一個(gè)數(shù)據(jù)包的平均能量消耗

由圖7可知，F(xiàn)TCD路由的標(biāo)準(zhǔn)偏差曲線變化平衡，波動小，且小于DEBR, FTCA, MHRM路由的標(biāo)準(zhǔn)偏差，充分說明FTCD路由的能量消耗更平衡。此外，還可比較四個(gè)路由錯(cuò)誤的傳感節(jié)點(diǎn)數(shù)。如果傳感節(jié)點(diǎn)的剩余能量不為零，且至少一個(gè)CH在其通信范圍內(nèi)，這樣的傳感節(jié)點(diǎn)被認(rèn)為是正常的傳感節(jié)點(diǎn)，否則被認(rèn)為是錯(cuò)誤的傳感節(jié)點(diǎn)。FTCD路由錯(cuò)誤的傳感節(jié)點(diǎn)數(shù)少于DEBR, FTCA, MHRM路由錯(cuò)誤的傳感節(jié)點(diǎn)數(shù)，且隨Round的增加而增加的步伐減緩。這主要是因?yàn)镕TCD路由考慮了傳感節(jié)點(diǎn)的能量消息。

圖7 CH剩余能量的標(biāo)準(zhǔn)偏差及錯(cuò)誤的傳感節(jié)點(diǎn)數(shù)

5 結(jié) 論

針對無線傳感網(wǎng)絡(luò)數(shù)據(jù)傳輸問題，提出FTCD路由。FTCD路由引用簇化的分布式路由理念，充分考慮了簇頭錯(cuò)誤情況，初始階段簇頭先廣播HELLO消息，傳感節(jié)點(diǎn)計(jì)算選擇不同簇頭的增益，提出容錯(cuò)處理算法。仿真實(shí)驗(yàn)結(jié)果表明，F(xiàn)TCD路由能有效應(yīng)對簇頭錯(cuò)誤，提高了能量利用率。下一步將研究基于簇的路由機(jī)制，將其拓展至任何一個(gè)分布式路由協(xié)議，進(jìn)而提高路由協(xié)議的性能。

[1] 楊明霞，王萬良，馬晨明.面向節(jié)能和容錯(cuò)的異構(gòu)WSNs數(shù)據(jù)收集算法[J].傳感技術(shù)學(xué)報(bào)，2016（6）：934-940.

[2] M ISRA S，KRISHNA P V，SARITHA V.LACAV：an Energy-Ef f cient Channel Assignment Mechanism for Vehicular ad Hoc Networks[J]. The Journal of Supercomputing，2012（3）：1241-1262.

[3] 王莘.一種無線傳感網(wǎng)絡(luò)節(jié)能分簇算法[J].電子測試，2014（5）：50-52.

[4] 沈艷霞，薛小松.無線傳感網(wǎng)絡(luò)移動信標(biāo)節(jié)點(diǎn)路徑優(yōu)化策略[J].傳感器與微系統(tǒng)，2012（12）：42-44.

[5] 歸奕紅.無線傳感器網(wǎng)絡(luò)HEDSA數(shù)據(jù)聚合研究[J].計(jì)算機(jī)工程，2011（7）：160-162.

[6] 周磊，董乃銘，洪振杰.UKF算法與SVDKF算法性能的比較[J].溫州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2013（1）：81-83.

[7] KUILA P，JANA P K.Energy Ef f cient Load-balanced Clustering A lgorithm for W ireless Sensor Network[J].Procedia Technology，2012（4）：771-777.

[8] 羅四維，侯孟書，周益民.一種新的基于能量消耗速率模型的分簇路由協(xié)議[J].計(jì)算機(jī)科學(xué)，2012（6）：47-50.

[9] CHIANG S S，HUANG C H，CHANG K C. A M inimum Hop Routing Protocol for Home Security Systems Using Wireless Sensor Networks[J]. IEEE Transactions on Consumer Electronics，2007（4）：1483-1489.

[10] BANERJEE I，CHANAK P，RAHAMAN H A，et al.Effective Fault Detection and Routing Scheme for Wireless Sensor Networks[J]. Computers & Electrical Engineering，2014（2）：291-306.

[責(zé)任編輯：田啟明]

Cluster-based Routing Algorithm for W ireless Sensor Networks

HOU Aixia
(School of Mechanic and Electronic Engineering, Chongqing Creation Vocational College, Chongqing, 402160, China)

Sensor nodes are very prone to failure due to several factors such as environmental hazards, energy depletion and device failure, which affects the application performance of WSNs and the overall network lifetime. In order to solve the problem of sensor node failure, the paper proposes a fault-tolerant and clustering-based distributed (FTCD) rouging in WSNs. In the clustering phase, sensor nodes select its CH on the basis of the distance between sensor node and the CH, the distance from the CH to the base station, and the residual energy of the CH. In data routing phase, the CHs select their next hop neighbor CH in such a way that their energy consumption w ill be balanced and minimized. The simulation experiment shows that the FTCD roughing can cope w ith the sensor node failure effectively, and increase the energy ef f ciency so as to improve the performance in various other aspects.

WSNs; FTCD; CH; Sensor nodes

TN929.5; TP212.9

A

1671-4326 (2017) 02-0051-05

DO I: 10.13669/j.cnki.33-1276/z.2017.034

2016-12-28

侯愛霞（1981—），女，湖北襄陽人，重慶科創(chuàng)職業(yè)學(xué)院信息與機(jī)電工程學(xué)院講師，碩士.