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

侯愛霞

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

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

侯愛霞

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

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

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

1 問題的提出

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（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é)點集CO：若在傳感節(jié)點si的通信范圍內(nèi)，至少存在一個CH，那么si屬于傳感節(jié)點集CO；若在傳感節(jié)點si的通信范圍內(nèi)，不存在CH，那么si屬于非傳感節(jié)點集UnCO，則：

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

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

3 FTCD協(xié)議

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

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

3.1 初始階段

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

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

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

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

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

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

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

圖3 簇的形成算法流程

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

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

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

3.3 容錯性分析

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

圖4 容錯處理算法流程

4 仿真實驗

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

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

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

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

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

4.3 CH剩余能量的標準偏差和錯誤的傳感節(jié)點數(shù)

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

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

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

圖7 CH剩余能量的標準偏差及錯誤的傳感節(jié)點數(shù)

5 結 論

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

[1] 楊明霞，王萬良，馬晨明.面向節(jié)能和容錯的異構WSNs數(shù)據(jù)收集算法[J].傳感技術學報，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)絡節(jié)能分簇算法[J].電子測試，2014（5）：50-52.

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

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

[6] 周磊，董乃銘，洪振杰.UKF算法與SVDKF算法性能的比較[J].溫州職業(yè)技術學院學報，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].計算機科學，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.

[責任編輯：田啟明]

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è)學院信息與機電工程學院講師，碩士.