仿血管路徑的無線傳感器網絡故障容錯路由算法?

李洪兵，余成波，全曉莉，劉峪王宣

仿血管路徑的無線傳感器網絡故障容錯路由算法?

李洪兵1，2，余成波1，全曉莉1，劉峪王宣1

（1.重慶理工大學遠程測試與控制技術研究所，重慶400054；2.重慶三峽學院，重慶404000）

為提高無線傳感器網絡故障容錯性和傳輸穩定性，實現網絡負載均衡，提出了一種仿血管路徑的無線傳感器網絡故障容錯路由算法。研究了人體血管路徑特性及屬性關聯，對網絡節點分區域等級標定并以不同概率值進行靜態分簇，運用改進的蟻群算法BWAS（最優最差螞蟻系統）生成節點路徑，以路徑信息素值作為傳輸路徑的選擇概率建立仿血管拓撲結構路由。因具有多條傳輸路徑并選擇最高概率作為傳輸路由，避免了因節點或鏈路故障導致數據的延遲或丟失，提高了網絡故障容錯性和傳輸穩定性，實現了網絡能耗均衡。理論分析和仿真結果表明此算法具有良好性能。

無線傳感器網絡；故障容錯；路由協議；血管路徑；BWAS算法

1 引言

因拓撲動態變化、能量約束和傳輸受限等特性，無線傳感器網絡（Wireless Sensor Network，WSN）易出現多種網路故障，如節點失效、鏈路質量差、數據碰撞厲害、能耗不均和網絡魯棒性差等。無線傳感器網絡自身的健康狀態對于獲取準確的數據極為重要，病態的無線傳感器網絡較難協調處理和獲取可靠的數據。故障容錯是無線傳感器網絡面臨著的一個共性的、亟待解決的關鍵性技術問題。無線傳感器自身故障容錯研究尚處于初始階段，研究其容錯路由算法、提高無線傳感器網絡運行的穩定性是非常必要的。

國內外對無線傳感器網路自身故障診斷與容錯作了一定的研究，提出的較典型的容錯路由協議和算法有：引入故障節點繞行機制實時容錯路由協議FT－SPEED［1］；具有多拓撲路由的入侵容錯路由協議SEIF［2］；具有負載均衡的延遲容錯跨層數據傳輸協議LOFT［3］；動態分布式簇頭選舉故障容錯算法FTEP［4］；基于TDMA協議同步并提供數據在傳輸過程中首位相連的保證機制FlexiTP［5］；前向錯誤糾正編碼算法［6］；FTPASC算法［7］；延長射頻傳輸范圍的平面路由［8］和故障容錯動態分簇協議FT－DSC［9］等。它們在無線傳感器網絡故障容錯方面取得了較好的效果，但以增加算法復雜度、增加能量消耗、降低靈活性及穩定性的某些方面為代價。

本文根據人體血管路徑分布特征以及對無線傳感器網絡故障容錯的啟示，基于特性條件約束，賦予人為定義并優化，擬采用改進的蟻群算法仿真人體血管拓撲結構路由，開展能故障容錯的無線傳感器網絡仿人體血管拓撲結構路由算法研究。

2 WSN仿血管拓撲結構路由的屬性關聯與特征

2.1 WSN仿血管拓撲結構路由的屬性關聯分析

人體血管路徑與血流流動具有如下特性：（1）血管具有相對穩定和局部彈性，主要血流量沿著動脈血管路徑流動，血液在局部范圍可繞行流動；（2）血管路徑具有空間連通性，具有實際流動路徑和可被選流動路徑，某處血管發生病變，血液會選擇合適的路徑繞行流動；（3）血管交叉點的血壓大小不一，血液根據血流流變學原理沿血管路徑定向流動；（4）血液流量、流速和血管截面與血壓參數間有著定量的關系。

無線傳感器網絡與人體血管血流的特征關聯：（1）心臟搏跳過程與匯聚節點廣播消息、采集、匯集和傳輸數據的周期性工作機制與時間同步性；（2）血液攜帶營養物質沿體動脈到毛細血管流動過程與匯聚節點沿著一定路徑廣播消息給各傳感器節點；（3）靜脈血液回流至右心房過程與傳感器節點收集信息傳輸至匯聚節點過程；（4）血液在血管交叉處匯集與無線傳感器數據聚集或融合等。

人體血管血流特性對建立無線傳感器網絡故障容錯路由的啟示：（1）所建立的仿血管拓撲結構路由應具有多路徑連通性；（2）建立有等級區別的節點以保證數據的有向傳輸；（3）用蟻群算法在路徑尋優中的信息素值確定數據傳輸時最優路徑的選擇問題；（4）不同等級節點采用不同概率分簇，避免無線傳感器網絡熱點問題。

2.2 WSN仿血管拓撲結構路由特征

根據人體血管路徑特征所建立的仿血管拓撲結構路由示意圖如圖1所示。其中，圖1（a）為仿血管路由邏輯拓撲結構，圖1（b）為仿血管路由物理拓撲結構，圖1（c）為傳統樹型路由結構，節點0為網絡匯聚節點，節點1～10為網絡簇頭節點。

在仿血管路由邏輯拓撲結構中，一個節點不與同級節點建立路徑，只與鄰級簇頭節點建立傳輸路徑，且與在其發射功率覆蓋范圍的每個鄰級節點都建立傳輸路徑。節點1～5為第一級，負責簇內數據融合和接收并轉發來自第二級簇頭節點的數據至匯聚節點。節點6～8為第二級，負責簇內數據融合并轉發來自第三級簇頭節點數據至第一級節點。節點9和節點10為第三級，只負責簇內數據融合并將數據轉發至第二級節點。

在仿血管路由物理拓撲結構中，數據傳輸和消息廣播都具有方向性，簇頭節點與在其發射功率覆蓋范圍的所有鄰級節點都建立了路徑關系，各路徑信息素值大小不一，將其歸一化后數值作為數據傳輸的路徑選擇概率，選取最大概率值鏈路作為傳輸路徑。當傳輸路徑發生故障時，節點選擇次概率值鏈路作為傳輸路徑并依此類推。信息素是蟻群在搜尋最優路徑過程中在各路徑上留下的信息素濃度，是反映最優路徑的一個重要參數，如圖1（b）所示，不同顏色和線狀的路徑代表不同的信息素值，節點7選擇信息素值最大鏈路經節點3后傳至匯聚節點；若節點3發生故障，會選擇到節點2和4中較大信息素值鏈路作為傳輸路徑。

在傳統樹型路由結構中，樹結構中的節點只能向自身的父節點進行數據傳輸，存在較大節點風險問題。如節點3發生故障，則節點7、9、10的數據都將丟失，對整個網絡的數據準確性產生較大的影響。

3 WSN仿血管拓撲結構路由生成

3.1 基于等級區域劃分的靜態分簇

條件假設：（1）網絡節點是靜止的；（2）各節點的地理位置已知；（3）分簇前各傳感器節點地位平等，擁有相同的參數和初始能量；（4）網絡節點數量較大，都是全雙工工作模式；（5）節點隨機均勻分布在矩形區域內，匯聚節點位于外側。

分簇原理：為實現無線傳感器網絡能量均衡，避免距離匯聚節點近的簇頭節點因轉發數據負荷量大而提前死亡的熱點問題，通過與匯聚節點的距離將網絡節點分成不同等級區域，并將網絡節點進行等級標定，不同等級區域采用不同的簇頭選舉概率進行靜態分簇，構建大小不同的簇。簇內根據剩余能量動態輪換選舉簇頭，以實現能耗均衡。

分簇過程及特征：節點位置已知的無線傳感器網絡，以匯聚節點為中心，以半徑n·R（n∈1，2，…）將WSN劃分為不同的環狀區域，并將同一環狀區域的無線傳感器節點標定為同一等級。簇頭節點只能建立到鄰級節點的路由，不能與同級節點建立路由。每個區域以不同的概率選舉簇頭。靠近匯聚節點的區域為第一等級，以較大概率選取簇頭，各等級依次減小，并最終形成距離匯聚節點越近的區域，簇頭數量較多、簇規模較小的格局，如圖2所示。距離匯聚節點較近的區域，形成的簇的規模較小，簇頭消耗在簇內通信和數據聚合上的能量較少，以補償轉發其它區域簇頭節點數據包的能量消耗。距離匯聚節點較遠區域，形成的簇的規模較大，簇內通信和數據聚合上的能耗增大，以抵消轉發較少的數據包而節省的能量，最終實現能耗均衡［10］。

簇頭選取概率確定：網絡能耗參考文獻［11］，當分成n個區域時，每個區域半徑為n·R，傳感器節點總數為Nn·R。從半徑為R區域開始每個區域簇頭選取概率為pn（n∈1，2…），則每個區域簇頭數為，一個簇內非簇頭節點總數－1。現假設每個節點只發送k bit數據，則在半徑為R等級區域內，一個簇頭節點能耗：

簇內非簇頭節點能耗：

一個簇的總能耗：

要使得總能耗最小，有：

得p1。根據能耗均衡要求，ER·total＝E2R·total，故能求得p2，并依此類推。

3.2 基于BWAS的路徑信息素值的計算

最優最差螞蟻系統（Best-worst Ant system，BWAS）［12］是對蟻群算法的改進，引入對最差螞蟻懲罰機制，在所有螞蟻完成一次循環后，對最差螞蟻所經過的且非最優螞蟻路徑的路徑信息素進行更新，進一步增大最優與最差螞蟻的信息素，增強了最優路徑搜索過程指導，加快收斂速度。假設在每個簇頭節點置放一定數量人工螞蟻，定義每只螞蟻的任務是搜尋從所在簇頭節點到匯聚節點的一條路徑，螞蟻完成任務時立即死亡。螞蟻具有記憶所走過路徑信息素值的功能。算法基本步驟如下：

第一步初始化參數。確定簇頭節點信息，設定每個簇頭節點的人工螞蟻數量、定義其屬性等。

第二步根據式（5）和式（6）為每只螞蟻選擇路徑：

第三步每只螞蟻完成任務后，網絡對其生成的路徑按式（9）進行一次局部更新；

式中，τ（r，s）表示節點r到節點s之間的信息素軌跡量，ρ為一個參數，0＜ρ＜1，n為節點數量，Lnn為最近的領域啟發產生的一個路徑長度。

第四步循環執行第二步、第三步直到簇頭節點中的每只螞蟻都生成—條路徑。

第五步根據所在簇頭節點的每只螞蟻經歷路徑的長度，評選出最優螞蟻和最差螞蟻。

第六步對最優螞蟻按式（11）執行全局更新規則：

其中：

第七步對最差螞蟻按式（13）執行全局更新規則：

式中，ε為該算法中引入的一個參數，Lworst為當前循環中最差螞蟻的路徑長度，Lbest為當前循環中最優螞蟻的路徑長度，τ（r，s）為節點r和節點s之間的信息素軌跡量，Lgb為當前循環中找出的全局最優路徑，α為信息素揮發參數，0＜α＜1。

第八步分別對其余簇頭節點中的螞蟻執行第2～7步，直到所有簇頭節點的螞蟻運行完畢，記錄出各路徑信息素值。圖3所示為BW AS算法步驟流程。

3.3 建立傳輸路由與工作機制

仿血管拓撲結構路由主要在于提高鏈路質量和容錯性，提高數據傳輸的穩定性。對于能量有限的網絡，提高能量利用效率是其關鍵技術。在等級標定、靜態分簇、運用BWAS算法計算出各路徑的信息素值后，將各路徑信息素值歸一化，作為建立傳輸路徑的選擇概率。在此仿血管拓撲結構路由中，當某簇頭節點能量消耗達到一定閾值時，主動沿原路徑報告信息，以減少信息廣播傳輸能耗。等待傳輸周期完畢，簇內根據能量均衡原則動態輪換選舉能量較高的節點擔當簇頭節點，整個網絡運用BWAS算法進行新一輪的路徑信息素的計算，以建立新的拓撲結構路由。

4 仿血管拓撲結構路由仿真與性能評價

4.1 仿血管拓撲結構路由仿真

基于Matlab平臺仿真，首先隨機生成分區域等級標定的無線傳感器節點，靜態分簇后每個簇頭節點置放10只螞蟻，按照BWAS算法步驟對傳感器節點進行仿真。當所有節點的螞蟻都到達匯聚節點完成任務時，各路徑信息素進行全局更新，BWAS算法循環結束，各路徑信息素停止揮發，記錄各路徑信息素值。路徑仿真結果如圖4和圖5所示。

圖4和圖5分別為仿血管路由的物理拓撲結構和邏輯拓撲結構。由圖4和圖5可知，螞蟻在BWAS算法下走過的路徑，記錄下各路徑信息素值，并記錄在傳感器節點上。螞蟻所走過的路徑是沒有分等級節點的，是在所有節點平等的地位上展開的群體智能搜索。根據蟻群算法基本原理，信息素的濃度反映了蟻群搜索最優路徑的結果。根據仿血管拓撲結構特征，即有等級區別的、簇頭節點只和鄰級簇頭節點建立傳輸路徑的特征，建立了整個網絡傳輸的拓撲結構路由。

4.2 仿血管拓撲結構路由性能評價

4.2.1 BWAS算法收斂速度

BWAS算法對蟻群算法的改進，是在蟻群搜尋最優路徑過程中，引入對最優最差螞蟻懲罰機制，增強了搜索過程指導，對最差螞蟻所經過的且非最優螞蟻路徑的路徑信息素進行更新，進一步增大最優與最差螞蟻的信息素，加快收斂速度，提高了計算效率，節約了路徑尋優能耗。

4.2.2 能耗均衡性

根據距離匯聚節點遠近，將無線傳感器網絡分成具有等級的區域，不同等級區域的節點以不同的概率分簇，保證不同等級區域的傳感器節點總體能耗均衡，避免了距離匯集節點近的節點因轉發大量數據而提前耗盡能量。簇內根據能量高低動態輪換選舉簇頭，有效保證了同一區域內各節點的能耗均衡。

取Ei，j（i＝1，2，3；j為數據傳輸輪數）為第i等級區域第j輪數據傳輸時總的剩余能量，ΔEi，j＝Ei，j－Ei，j＋100表示第i等級區域第j輪后的100輪的數據傳輸所消耗的能量，其能量消耗如圖6所示。

由圖6可知，當無線傳感器網絡數據傳輸輪數在300～700之間，第1、2、3等級區域的總能耗值在［495，520］之間，不同等級區域總體能耗均衡，避免了無線傳感器網絡熱點問題。

4.2.3 路由容錯性

任一簇頭節點都與在其發射功率覆蓋范圍的鄰級簇頭節點建立了路徑，只選擇其最大概率值路徑作為傳輸路徑。一旦發生節點或鏈路故障，網絡會選擇次概率值路徑進行傳輸。在圖1中以節點7為例，節點7建立起到鄰級節點1～5的路徑pathi（i＝1，2，…，5），但這5條路徑對應的選擇概率pi≠pj（i≠j；i、j＝1，2，…，5）。建立的實際傳輸路徑為pathj→max（pi），i＝1，2，…，5，但當此鏈路發生故障時，實際傳輸路徑就改為pathk→max（pi），i≠j，i＝1，2，…，5，并以此類推。因此，任何一個等級區域的節點都能按照概率建立到匯聚節點的最優路徑，提高了鏈路容錯性，保證了數據傳輸的穩定性，降低了數據在傳統樹結構路由中傳輸的風險。

5 結論

根據血管路徑具有的相對穩定性、局部彈性、空間連通性及血液定向流動特性，對網絡節點分區域等級標定，以不同概率值進行靜態分簇，運用改進的蟻群算法BWAS生成節點路徑，將路徑信息素歸一化后作為實際傳輸路徑的選擇概率而建立仿血管拓撲結構路由。此算法提高了網絡故障容錯性和數據傳輸穩定性，均衡了網絡負載，延長了網絡生命期。

此算法是在前期BW AS算法優化研究基礎之上開展的無線傳感器網絡的路由研究，但在概率分簇和路由算法設計時是基于血管路徑特性。對于傳感器節點數量較大的網絡，此算法在能效均衡和容錯穩定等方面具有較好的性能，這在實際應用中具有重要的意義。作為一種新穎的路由算法，在理論分析、體系完善并得到實際應用的過程中還有諸多方面值得深入研究，如在不同情況下等級分簇的能效性判定、數據傳輸的有效性以及數據傳輸工作機制等。

［1］Lei Zhao，Baoqiang Kan，Yongjun Xu，et al.FT-SPEED：A Fault-Tolerant，Real-Time Routing Protocol for Wireless Sensor Networks［C］／／Proceedings of 2007 International Conference on Wireless Communications，Networking and Mobile Computing.［S.l.］：IEEE，2007：2531－2534.

［2］Ouadjaout A，Challal Y，Lasla N，et al.SEIF：Secure and Efficient Intrusion-Fault Tolerant Routing Protocol for Wireless Sensor Networks［C］／／Proceedings of 2008 3th International Conference on Availability，Reliability and Security.［S.l.］：IEEE，2008：503－508.

［3］Ngai E C－H，Zhou Yangfan，Lyu M R，et al.LOFT：A Latency-Oriented Fault Tolerant Transport Protocol for Wireless Sensor-Actuator Networks［C］／／Proceedings of 2007 Global Telecommunications Conference.Washington，DC：IEEE，2007：1318－1323.

［4］Bansal N，Sharma T P，Misra M，et al.FTEP：A fault tolerant election protocol for multi-level clustering in homogeneous wireless sensor networks［C］／／Proceedings of 16th International Conference on Networks.New Delhi：IEEE，2008：1－6.

［5］Lee W L，Datta A，Cardell-Oliver R.FlexiTP：A Flexible-Schedule-Based TDMA Protocol for Fault-Tolerant and Energy-Efficient Wireless Sensor Networks［J］.Transactions on Parallel and Distributed Systems，2008，19（6）：851－864.

［6］Zhiqiang Xiong，ZongkaiYang，WeiLiu，etal.A Lightweight FEC Algorithm for Fault Tolerant Routing in Wireless Sensor Networks［C］／／Proceedings of 2006 International Conference on Wireless Communications，Networking and Mobile Computing.Wuhan：IEEE，2006：1－4.

［7］Khadivi A，Shiva M.FTPASC：A Fault Tolerant Power Aware Protocol with Static Clustering for Wireless Sensor Networks［C］／／Proceedings of 2006 IEEE International Conference on Wireless and Mobile Computing，Networking and Communications.Montreal，Que：IEEE，2006：397－401.

［8］Xin-Ming Huang，Jing Deng，Jing M，et al.Fault tolerant routing for wireless sensor grid networks［C］／／Proceedings of 2006 IEEE Sensors Applications Symposium.Luoyang：IEEE，2006：66－70.

［9］Karim Lutful，Nasser Nidal，Sheltami Tarek.A Fault Tolerant Dynamic Clustering Protocol of Wireless Sensor Networks［C］／／Proceedings of 2009 IEEE International Conference on Global Telecommunications.Honolulu，HI：IEEE，2009：1－6.

［10］劉志，裘正定.基于分環多跳的無線傳感網分簇路由算法［J］.通信學報，2008，29（3）：104－113.

LIU Zhi，QIU Zheng－ding.Ring based multi－hop clustering routing algorithm for wireless sensor networks［J］.Journal on Communications，2008，29（3）：104－113.（in Chinese）

［11］Lindsey Stephanie，Raghavendra CauligiSivalingam，Krishna M.Data Gathering Algorithms in Sensor Networks Using Energy Metrics［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（9）：924－935.

［12］李洪兵，余成波，陳強，等.基于BW AS的無線傳感器網絡靜態分簇路由算法［J］.電訊技術，2010，50（4）：96－101.

LI Hong-bing，YU Cheng-bo，CHEN Qiang，et al.Static Clustering Routing Algorithm Based on Best Worst Ant System for Wireless Sensor Networks［J］.Telecommunication Engineering，2010，50（4）：96－101.（in Chinese）

LI Hong－bing was born in Tongnan，Chongqing，in 1981.He is now a lecturer and also a graduate student.His research interests include intelligent signal processing and wireless sensor network.

Email：sxxylhb＠163.com

余成波（1965－），男，博士，教授，重慶理工大學碩士生導師，中北大學博士生導師，重慶市學術技術帶頭人。主要研究領域為信息獲取與處理技術、遠程測試與控制技術和車輛電子技術；

YU Cheng－bo was born in 1965.He is now a professor with the Ph.D.degree.He is master tutor of Chongqing University of Technology and also the Ph.D.supervisor of North University of China，leader of Chongqing academic and technology.His research interests include information acquisition and processing，remote testing and controlling technology and vehicle electronics.

Email：yuchengbo＠cqut.edu.cn

全曉莉（1975－），女，重慶潼南人，碩士研究生，講師，主要研究方向為信號處理、虛擬儀器軟件開發；

QUAN Xiao－li was born in Tongnan，Chongqing，in 1975. She is now a lecturer and also a graduate student.Her research interests include signal processing and virtual instrument software development.

Email：znq55555＠163.com

劉峪王宣（1986－），男，江蘇儀征人，碩士研究生，主要研究方向為無線傳感器網絡。

LIU Yu－xuan was born in Yizheng，Jiangsu Province，in 1986.He is now a graduate student.His research direction is wireless sensor network.

Email：biergaici2025＠126.com

Fault-Tolerant Vascular Routing Algorithm for Wireless Sensor Networks

LI Hong-bing1，2，YU Cheng-bo1，QUAN Xiao-li1，LIU Yu-xuan1
（1.Research Institute of Remote Test and Control，Chongqing University of Technology，Chongqing 400054，China；2.Chongqing Three Gorges University，Chongqing 404000，China）

In order to enhance fault tolerance and transmission stability of wireless sensor networks（WSNs），as well as the network loads balance，a fault tolerant routing algorithm imitating human blood vessel is presented. The properties of human blood vessels are stndied，and static clustering is performed by using the different probabilities after the nodes of the network are marked with different grades.Best-Worst Ant System（BWAS），an improved ant colony algorithm，is used to generate the paths and calculate the paths′pheromones as to be the probability of the path selection.So the vascular routing is established.It has more than one transmission paths and chooses the path of highest probability to establish the actual transmission route.It avoids the data losses or delay caused by the failures of nodes or links，improves the fault tolerance of the network as well as the transmission stability，balances the power consumption in the whole network.Analysis and simulation show that the algorithm has good performance.

wireless sensor network（WSN）；fault tolerance；routing protocol；blood vessel；BWAS algorithm

The Natural Science Foundation of Chongqing（CSTC2007BA2023）；Science and Technology Project of Jiulongpo，Chongqing（Science and Technology Commission of Jiulongpo［2009］52）；Science and Technology Innovation Project of Chongqing（Economic and Information Technology of Chongqing［2010］9）；Science and Technology Project of Wanzhou，Chongqing（Science and Technology Commission of Wanzhou［2010］23）

TP393；TP212

A

10.3969／j.issn.1001－893x.2011.02.011

李洪兵（1981－），男，重慶潼南人，碩士研究生，講師，主要研究方向為智能信號處理、無線傳感器網絡；

1001－893X（2011）02－0056－06

2010－10－21；

2010－12－08

重慶市自然科學基金重點項目（CSTC2007BA2023）；重慶市九龍坡科技計劃項目（九龍坡科委發［2009］52號）；重慶市科技創新項目（渝經信科技［2010］9號）；重慶市萬州科技計劃項目（萬州科委［2010］23號）