仿血管路徑的無(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)路由算法?

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

仿血管路徑的無(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)路由算法?

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

（1.重慶理工大學(xué)遠(yuǎn)程測(cè)試與控制技術(shù)研究所，重慶400054；2.重慶三峽學(xué)院，重慶404000）

為提高無(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)性和傳輸穩(wěn)定性，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，提出了一種仿血管路徑的無(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)路由算法。研究了人體血管路徑特性及屬性關(guān)聯(lián)，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)分區(qū)域等級(jí)標(biāo)定并以不同概率值進(jìn)行靜態(tài)分簇，運(yùn)用改進(jìn)的蟻群算法BWAS（最優(yōu)最差螞蟻系統(tǒng)）生成節(jié)點(diǎn)路徑，以路徑信息素值作為傳輸路徑的選擇概率建立仿血管拓?fù)浣Y(jié)構(gòu)路由。因具有多條傳輸路徑并選擇最高概率作為傳輸路由，避免了因節(jié)點(diǎn)或鏈路故障導(dǎo)致數(shù)據(jù)的延遲或丟失，提高了網(wǎng)絡(luò)故障容錯(cuò)性和傳輸穩(wěn)定性，實(shí)現(xiàn)了網(wǎng)絡(luò)能耗均衡。理論分析和仿真結(jié)果表明此算法具有良好性能。

無(wú)線傳感器網(wǎng)絡(luò)；故障容錯(cuò)；路由協(xié)議；血管路徑；BWAS算法

1 引言

因拓?fù)鋭?dòng)態(tài)變化、能量約束和傳輸受限等特性，無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）易出現(xiàn)多種網(wǎng)路故障，如節(jié)點(diǎn)失效、鏈路質(zhì)量差、數(shù)據(jù)碰撞厲害、能耗不均和網(wǎng)絡(luò)魯棒性差等。無(wú)線傳感器網(wǎng)絡(luò)自身的健康狀態(tài)對(duì)于獲取準(zhǔn)確的數(shù)據(jù)極為重要，病態(tài)的無(wú)線傳感器網(wǎng)絡(luò)較難協(xié)調(diào)處理和獲取可靠的數(shù)據(jù)。故障容錯(cuò)是無(wú)線傳感器網(wǎng)絡(luò)面臨著的一個(gè)共性的、亟待解決的關(guān)鍵性技術(shù)問(wèn)題。無(wú)線傳感器自身故障容錯(cuò)研究尚處于初始階段，研究其容錯(cuò)路由算法、提高無(wú)線傳感器網(wǎng)絡(luò)運(yùn)行的穩(wěn)定性是非常必要的。

國(guó)內(nèi)外對(duì)無(wú)線傳感器網(wǎng)路自身故障診斷與容錯(cuò)作了一定的研究，提出的較典型的容錯(cuò)路由協(xié)議和算法有：引入故障節(jié)點(diǎn)繞行機(jī)制實(shí)時(shí)容錯(cuò)路由協(xié)議FT－SPEED［1］；具有多拓?fù)渎酚傻娜肭秩蒎e(cuò)路由協(xié)議SEIF［2］；具有負(fù)載均衡的延遲容錯(cuò)跨層數(shù)據(jù)傳輸協(xié)議LOFT［3］；動(dòng)態(tài)分布式簇頭選舉故障容錯(cuò)算法FTEP［4］；基于TDMA協(xié)議同步并提供數(shù)據(jù)在傳輸過(guò)程中首位相連的保證機(jī)制FlexiTP［5］；前向錯(cuò)誤糾正編碼算法［6］；FTPASC算法［7］；延長(zhǎng)射頻傳輸范圍的平面路由［8］和故障容錯(cuò)動(dòng)態(tài)分簇協(xié)議FT－DSC［9］等。它們?cè)跓o(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)方面取得了較好的效果，但以增加算法復(fù)雜度、增加能量消耗、降低靈活性及穩(wěn)定性的某些方面為代價(jià)。

本文根據(jù)人體血管路徑分布特征以及對(duì)無(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)的啟示，基于特性條件約束，賦予人為定義并優(yōu)化，擬采用改進(jìn)的蟻群算法仿真人體血管拓?fù)浣Y(jié)構(gòu)路由，開(kāi)展能故障容錯(cuò)的無(wú)線傳感器網(wǎng)絡(luò)仿人體血管拓?fù)浣Y(jié)構(gòu)路由算法研究。

2 WSN仿血管拓?fù)浣Y(jié)構(gòu)路由的屬性關(guān)聯(lián)與特征

2.1 WSN仿血管拓?fù)浣Y(jié)構(gòu)路由的屬性關(guān)聯(lián)分析

人體血管路徑與血流流動(dòng)具有如下特性：（1）血管具有相對(duì)穩(wěn)定和局部彈性，主要血流量沿著動(dòng)脈血管路徑流動(dòng)，血液在局部范圍可繞行流動(dòng)；（2）血管路徑具有空間連通性，具有實(shí)際流動(dòng)路徑和可被選流動(dòng)路徑，某處血管發(fā)生病變，血液會(huì)選擇合適的路徑繞行流動(dòng)；（3）血管交叉點(diǎn)的血壓大小不一，血液根據(jù)血流流變學(xué)原理沿血管路徑定向流動(dòng)；（4）血液流量、流速和血管截面與血壓參數(shù)間有著定量的關(guān)系。

無(wú)線傳感器網(wǎng)絡(luò)與人體血管血流的特征關(guān)聯(lián)：（1）心臟搏跳過(guò)程與匯聚節(jié)點(diǎn)廣播消息、采集、匯集和傳輸數(shù)據(jù)的周期性工作機(jī)制與時(shí)間同步性；（2）血液攜帶營(yíng)養(yǎng)物質(zhì)沿體動(dòng)脈到毛細(xì)血管流動(dòng)過(guò)程與匯聚節(jié)點(diǎn)沿著一定路徑廣播消息給各傳感器節(jié)點(diǎn)；（3）靜脈血液回流至右心房過(guò)程與傳感器節(jié)點(diǎn)收集信息傳輸至匯聚節(jié)點(diǎn)過(guò)程；（4）血液在血管交叉處匯集與無(wú)線傳感器數(shù)據(jù)聚集或融合等。

人體血管血流特性對(duì)建立無(wú)線傳感器網(wǎng)絡(luò)故障容錯(cuò)路由的啟示：（1）所建立的仿血管拓?fù)浣Y(jié)構(gòu)路由應(yīng)具有多路徑連通性；（2）建立有等級(jí)區(qū)別的節(jié)點(diǎn)以保證數(shù)據(jù)的有向傳輸；（3）用蟻群算法在路徑尋優(yōu)中的信息素值確定數(shù)據(jù)傳輸時(shí)最優(yōu)路徑的選擇問(wèn)題；（4）不同等級(jí)節(jié)點(diǎn)采用不同概率分簇，避免無(wú)線傳感器網(wǎng)絡(luò)熱點(diǎn)問(wèn)題。

2.2 WSN仿血管拓?fù)浣Y(jié)構(gòu)路由特征

根據(jù)人體血管路徑特征所建立的仿血管拓?fù)浣Y(jié)構(gòu)路由示意圖如圖1所示。其中，圖1（a）為仿血管路由邏輯拓?fù)浣Y(jié)構(gòu)，圖1（b）為仿血管路由物理拓?fù)浣Y(jié)構(gòu)，圖1（c）為傳統(tǒng)樹(shù)型路由結(jié)構(gòu)，節(jié)點(diǎn)0為網(wǎng)絡(luò)匯聚節(jié)點(diǎn)，節(jié)點(diǎn)1～10為網(wǎng)絡(luò)簇頭節(jié)點(diǎn)。

在仿血管路由邏輯拓?fù)浣Y(jié)構(gòu)中，一個(gè)節(jié)點(diǎn)不與同級(jí)節(jié)點(diǎn)建立路徑，只與鄰級(jí)簇頭節(jié)點(diǎn)建立傳輸路徑，且與在其發(fā)射功率覆蓋范圍的每個(gè)鄰級(jí)節(jié)點(diǎn)都建立傳輸路徑。節(jié)點(diǎn)1～5為第一級(jí)，負(fù)責(zé)簇內(nèi)數(shù)據(jù)融合和接收并轉(zhuǎn)發(fā)來(lái)自第二級(jí)簇頭節(jié)點(diǎn)的數(shù)據(jù)至匯聚節(jié)點(diǎn)。節(jié)點(diǎn)6～8為第二級(jí)，負(fù)責(zé)簇內(nèi)數(shù)據(jù)融合并轉(zhuǎn)發(fā)來(lái)自第三級(jí)簇頭節(jié)點(diǎn)數(shù)據(jù)至第一級(jí)節(jié)點(diǎn)。節(jié)點(diǎn)9和節(jié)點(diǎn)10為第三級(jí)，只負(fù)責(zé)簇內(nèi)數(shù)據(jù)融合并將數(shù)據(jù)轉(zhuǎn)發(fā)至第二級(jí)節(jié)點(diǎn)。

在仿血管路由物理拓?fù)浣Y(jié)構(gòu)中，數(shù)據(jù)傳輸和消息廣播都具有方向性，簇頭節(jié)點(diǎn)與在其發(fā)射功率覆蓋范圍的所有鄰級(jí)節(jié)點(diǎn)都建立了路徑關(guān)系，各路徑信息素值大小不一，將其歸一化后數(shù)值作為數(shù)據(jù)傳輸?shù)穆窂竭x擇概率，選取最大概率值鏈路作為傳輸路徑。當(dāng)傳輸路徑發(fā)生故障時(shí)，節(jié)點(diǎn)選擇次概率值鏈路作為傳輸路徑并依此類推。信息素是蟻群在搜尋最優(yōu)路徑過(guò)程中在各路徑上留下的信息素濃度，是反映最優(yōu)路徑的一個(gè)重要參數(shù)，如圖1（b）所示，不同顏色和線狀的路徑代表不同的信息素值，節(jié)點(diǎn)7選擇信息素值最大鏈路經(jīng)節(jié)點(diǎn)3后傳至匯聚節(jié)點(diǎn)；若節(jié)點(diǎn)3發(fā)生故障，會(huì)選擇到節(jié)點(diǎn)2和4中較大信息素值鏈路作為傳輸路徑。

在傳統(tǒng)樹(shù)型路由結(jié)構(gòu)中，樹(shù)結(jié)構(gòu)中的節(jié)點(diǎn)只能向自身的父節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，存在較大節(jié)點(diǎn)風(fēng)險(xiǎn)問(wèn)題。如節(jié)點(diǎn)3發(fā)生故障，則節(jié)點(diǎn)7、9、10的數(shù)據(jù)都將丟失，對(duì)整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)準(zhǔn)確性產(chǎn)生較大的影響。

3 WSN仿血管拓?fù)浣Y(jié)構(gòu)路由生成

3.1 基于等級(jí)區(qū)域劃分的靜態(tài)分簇

條件假設(shè)：（1）網(wǎng)絡(luò)節(jié)點(diǎn)是靜止的；（2）各節(jié)點(diǎn)的地理位置已知；（3）分簇前各傳感器節(jié)點(diǎn)地位平等，擁有相同的參數(shù)和初始能量；（4）網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量較大，都是全雙工工作模式；（5）節(jié)點(diǎn)隨機(jī)均勻分布在矩形區(qū)域內(nèi)，匯聚節(jié)點(diǎn)位于外側(cè)。

分簇原理：為實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)能量均衡，避免距離匯聚節(jié)點(diǎn)近的簇頭節(jié)點(diǎn)因轉(zhuǎn)發(fā)數(shù)據(jù)負(fù)荷量大而提前死亡的熱點(diǎn)問(wèn)題，通過(guò)與匯聚節(jié)點(diǎn)的距離將網(wǎng)絡(luò)節(jié)點(diǎn)分成不同等級(jí)區(qū)域，并將網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行等級(jí)標(biāo)定，不同等級(jí)區(qū)域采用不同的簇頭選舉概率進(jìn)行靜態(tài)分簇，構(gòu)建大小不同的簇。簇內(nèi)根據(jù)剩余能量動(dòng)態(tài)輪換選舉簇頭，以實(shí)現(xiàn)能耗均衡。

分簇過(guò)程及特征：節(jié)點(diǎn)位置已知的無(wú)線傳感器網(wǎng)絡(luò)，以匯聚節(jié)點(diǎn)為中心，以半徑n·R（n∈1，2，…）將WSN劃分為不同的環(huán)狀區(qū)域，并將同一環(huán)狀區(qū)域的無(wú)線傳感器節(jié)點(diǎn)標(biāo)定為同一等級(jí)。簇頭節(jié)點(diǎn)只能建立到鄰級(jí)節(jié)點(diǎn)的路由，不能與同級(jí)節(jié)點(diǎn)建立路由。每個(gè)區(qū)域以不同的概率選舉簇頭。靠近匯聚節(jié)點(diǎn)的區(qū)域?yàn)榈谝坏燃?jí)，以較大概率選取簇頭，各等級(jí)依次減小，并最終形成距離匯聚節(jié)點(diǎn)越近的區(qū)域，簇頭數(shù)量較多、簇規(guī)模較小的格局，如圖2所示。距離匯聚節(jié)點(diǎn)較近的區(qū)域，形成的簇的規(guī)模較小，簇頭消耗在簇內(nèi)通信和數(shù)據(jù)聚合上的能量較少，以補(bǔ)償轉(zhuǎn)發(fā)其它區(qū)域簇頭節(jié)點(diǎn)數(shù)據(jù)包的能量消耗。距離匯聚節(jié)點(diǎn)較遠(yuǎn)區(qū)域，形成的簇的規(guī)模較大，簇內(nèi)通信和數(shù)據(jù)聚合上的能耗增大，以抵消轉(zhuǎn)發(fā)較少的數(shù)據(jù)包而節(jié)省的能量，最終實(shí)現(xiàn)能耗均衡［10］。

簇頭選取概率確定：網(wǎng)絡(luò)能耗參考文獻(xiàn)［11］，當(dāng)分成n個(gè)區(qū)域時(shí)，每個(gè)區(qū)域半徑為n·R，傳感器節(jié)點(diǎn)總數(shù)為Nn·R。從半徑為R區(qū)域開(kāi)始每個(gè)區(qū)域簇頭選取概率為pn（n∈1，2…），則每個(gè)區(qū)域簇頭數(shù)為，一個(gè)簇內(nèi)非簇頭節(jié)點(diǎn)總數(shù)－1。現(xiàn)假設(shè)每個(gè)節(jié)點(diǎn)只發(fā)送k bit數(shù)據(jù)，則在半徑為R等級(jí)區(qū)域內(nèi)，一個(gè)簇頭節(jié)點(diǎn)能耗：

簇內(nèi)非簇頭節(jié)點(diǎn)能耗：

一個(gè)簇的總能耗：

要使得總能耗最小，有：

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

3.2 基于BWAS的路徑信息素值的計(jì)算

最優(yōu)最差螞蟻系統(tǒng)（Best-worst Ant system，BWAS）［12］是對(duì)蟻群算法的改進(jìn)，引入對(duì)最差螞蟻懲罰機(jī)制，在所有螞蟻完成一次循環(huán)后，對(duì)最差螞蟻所經(jīng)過(guò)的且非最優(yōu)螞蟻路徑的路徑信息素進(jìn)行更新，進(jìn)一步增大最優(yōu)與最差螞蟻的信息素，增強(qiáng)了最優(yōu)路徑搜索過(guò)程指導(dǎo)，加快收斂速度。假設(shè)在每個(gè)簇頭節(jié)點(diǎn)置放一定數(shù)量人工螞蟻，定義每只螞蟻的任務(wù)是搜尋從所在簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的一條路徑，螞蟻完成任務(wù)時(shí)立即死亡。螞蟻具有記憶所走過(guò)路徑信息素值的功能。算法基本步驟如下：

第一步初始化參數(shù)。確定簇頭節(jié)點(diǎn)信息，設(shè)定每個(gè)簇頭節(jié)點(diǎn)的人工螞蟻數(shù)量、定義其屬性等。

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

第三步每只螞蟻完成任務(wù)后，網(wǎng)絡(luò)對(duì)其生成的路徑按式（9）進(jìn)行一次局部更新；

式中，τ（r，s）表示節(jié)點(diǎn)r到節(jié)點(diǎn)s之間的信息素軌跡量，ρ為一個(gè)參數(shù)，0＜ρ＜1，n為節(jié)點(diǎn)數(shù)量，Lnn為最近的領(lǐng)域啟發(fā)產(chǎn)生的一個(gè)路徑長(zhǎng)度。

第四步循環(huán)執(zhí)行第二步、第三步直到簇頭節(jié)點(diǎn)中的每只螞蟻都生成—條路徑。

第五步根據(jù)所在簇頭節(jié)點(diǎn)的每只螞蟻經(jīng)歷路徑的長(zhǎng)度，評(píng)選出最優(yōu)螞蟻和最差螞蟻。

第六步對(duì)最優(yōu)螞蟻按式（11）執(zhí)行全局更新規(guī)則：

其中：

第七步對(duì)最差螞蟻按式（13）執(zhí)行全局更新規(guī)則：

式中，ε為該算法中引入的一個(gè)參數(shù)，Lworst為當(dāng)前循環(huán)中最差螞蟻的路徑長(zhǎng)度，Lbest為當(dāng)前循環(huán)中最優(yōu)螞蟻的路徑長(zhǎng)度，τ（r，s）為節(jié)點(diǎn)r和節(jié)點(diǎn)s之間的信息素軌跡量，Lgb為當(dāng)前循環(huán)中找出的全局最優(yōu)路徑，α為信息素?fù)]發(fā)參數(shù)，0＜α＜1。

第八步分別對(duì)其余簇頭節(jié)點(diǎn)中的螞蟻執(zhí)行第2～7步，直到所有簇頭節(jié)點(diǎn)的螞蟻運(yùn)行完畢，記錄出各路徑信息素值。圖3所示為BW AS算法步驟流程。

3.3 建立傳輸路由與工作機(jī)制

仿血管拓?fù)浣Y(jié)構(gòu)路由主要在于提高鏈路質(zhì)量和容錯(cuò)性，提高數(shù)據(jù)傳輸?shù)姆€(wěn)定性。對(duì)于能量有限的網(wǎng)絡(luò)，提高能量利用效率是其關(guān)鍵技術(shù)。在等級(jí)標(biāo)定、靜態(tài)分簇、運(yùn)用BWAS算法計(jì)算出各路徑的信息素值后，將各路徑信息素值歸一化，作為建立傳輸路徑的選擇概率。在此仿血管拓?fù)浣Y(jié)構(gòu)路由中，當(dāng)某簇頭節(jié)點(diǎn)能量消耗達(dá)到一定閾值時(shí)，主動(dòng)沿原路徑報(bào)告信息，以減少信息廣播傳輸能耗。等待傳輸周期完畢，簇內(nèi)根據(jù)能量均衡原則動(dòng)態(tài)輪換選舉能量較高的節(jié)點(diǎn)擔(dān)當(dāng)簇頭節(jié)點(diǎn)，整個(gè)網(wǎng)絡(luò)運(yùn)用BWAS算法進(jìn)行新一輪的路徑信息素的計(jì)算，以建立新的拓?fù)浣Y(jié)構(gòu)路由。

4 仿血管拓?fù)浣Y(jié)構(gòu)路由仿真與性能評(píng)價(jià)

4.1 仿血管拓?fù)浣Y(jié)構(gòu)路由仿真

基于Matlab平臺(tái)仿真，首先隨機(jī)生成分區(qū)域等級(jí)標(biāo)定的無(wú)線傳感器節(jié)點(diǎn)，靜態(tài)分簇后每個(gè)簇頭節(jié)點(diǎn)置放10只螞蟻，按照BWAS算法步驟對(duì)傳感器節(jié)點(diǎn)進(jìn)行仿真。當(dāng)所有節(jié)點(diǎn)的螞蟻都到達(dá)匯聚節(jié)點(diǎn)完成任務(wù)時(shí)，各路徑信息素進(jìn)行全局更新，BWAS算法循環(huán)結(jié)束，各路徑信息素停止揮發(fā)，記錄各路徑信息素值。路徑仿真結(jié)果如圖4和圖5所示。

圖4和圖5分別為仿血管路由的物理拓?fù)浣Y(jié)構(gòu)和邏輯拓?fù)浣Y(jié)構(gòu)。由圖4和圖5可知，螞蟻在BWAS算法下走過(guò)的路徑，記錄下各路徑信息素值，并記錄在傳感器節(jié)點(diǎn)上。螞蟻所走過(guò)的路徑是沒(méi)有分等級(jí)節(jié)點(diǎn)的，是在所有節(jié)點(diǎn)平等的地位上展開(kāi)的群體智能搜索。根據(jù)蟻群算法基本原理，信息素的濃度反映了蟻群搜索最優(yōu)路徑的結(jié)果。根據(jù)仿血管拓?fù)浣Y(jié)構(gòu)特征，即有等級(jí)區(qū)別的、簇頭節(jié)點(diǎn)只和鄰級(jí)簇頭節(jié)點(diǎn)建立傳輸路徑的特征，建立了整個(gè)網(wǎng)絡(luò)傳輸?shù)耐負(fù)浣Y(jié)構(gòu)路由。

4.2 仿血管拓?fù)浣Y(jié)構(gòu)路由性能評(píng)價(jià)

4.2.1 BWAS算法收斂速度

BWAS算法對(duì)蟻群算法的改進(jìn)，是在蟻群搜尋最優(yōu)路徑過(guò)程中，引入對(duì)最優(yōu)最差螞蟻懲罰機(jī)制，增強(qiáng)了搜索過(guò)程指導(dǎo)，對(duì)最差螞蟻所經(jīng)過(guò)的且非最優(yōu)螞蟻路徑的路徑信息素進(jìn)行更新，進(jìn)一步增大最優(yōu)與最差螞蟻的信息素，加快收斂速度，提高了計(jì)算效率，節(jié)約了路徑尋優(yōu)能耗。

4.2.2 能耗均衡性

根據(jù)距離匯聚節(jié)點(diǎn)遠(yuǎn)近，將無(wú)線傳感器網(wǎng)絡(luò)分成具有等級(jí)的區(qū)域，不同等級(jí)區(qū)域的節(jié)點(diǎn)以不同的概率分簇，保證不同等級(jí)區(qū)域的傳感器節(jié)點(diǎn)總體能耗均衡，避免了距離匯集節(jié)點(diǎn)近的節(jié)點(diǎn)因轉(zhuǎn)發(fā)大量數(shù)據(jù)而提前耗盡能量。簇內(nèi)根據(jù)能量高低動(dòng)態(tài)輪換選舉簇頭，有效保證了同一區(qū)域內(nèi)各節(jié)點(diǎn)的能耗均衡。

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

由圖6可知，當(dāng)無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸輪數(shù)在300～700之間，第1、2、3等級(jí)區(qū)域的總能耗值在［495，520］之間，不同等級(jí)區(qū)域總體能耗均衡，避免了無(wú)線傳感器網(wǎng)絡(luò)熱點(diǎn)問(wèn)題。

4.2.3 路由容錯(cuò)性

任一簇頭節(jié)點(diǎn)都與在其發(fā)射功率覆蓋范圍的鄰級(jí)簇頭節(jié)點(diǎn)建立了路徑，只選擇其最大概率值路徑作為傳輸路徑。一旦發(fā)生節(jié)點(diǎn)或鏈路故障，網(wǎng)絡(luò)會(huì)選擇次概率值路徑進(jìn)行傳輸。在圖1中以節(jié)點(diǎn)7為例，節(jié)點(diǎn)7建立起到鄰級(jí)節(jié)點(diǎn)1～5的路徑pathi（i＝1，2，…，5），但這5條路徑對(duì)應(yīng)的選擇概率pi≠pj（i≠j；i、j＝1，2，…，5）。建立的實(shí)際傳輸路徑為pathj→max（pi），i＝1，2，…，5，但當(dāng)此鏈路發(fā)生故障時(shí)，實(shí)際傳輸路徑就改為pathk→max（pi），i≠j，i＝1，2，…，5，并以此類推。因此，任何一個(gè)等級(jí)區(qū)域的節(jié)點(diǎn)都能按照概率建立到匯聚節(jié)點(diǎn)的最優(yōu)路徑，提高了鏈路容錯(cuò)性，保證了數(shù)據(jù)傳輸?shù)姆€(wěn)定性，降低了數(shù)據(jù)在傳統(tǒng)樹(shù)結(jié)構(gòu)路由中傳輸?shù)娘L(fēng)險(xiǎn)。

5 結(jié)論

根據(jù)血管路徑具有的相對(duì)穩(wěn)定性、局部彈性、空間連通性及血液定向流動(dòng)特性，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)分區(qū)域等級(jí)標(biāo)定，以不同概率值進(jìn)行靜態(tài)分簇，運(yùn)用改進(jìn)的蟻群算法BWAS生成節(jié)點(diǎn)路徑，將路徑信息素歸一化后作為實(shí)際傳輸路徑的選擇概率而建立仿血管拓?fù)浣Y(jié)構(gòu)路由。此算法提高了網(wǎng)絡(luò)故障容錯(cuò)性和數(shù)據(jù)傳輸穩(wěn)定性，均衡了網(wǎng)絡(luò)負(fù)載，延長(zhǎng)了網(wǎng)絡(luò)生命期。

此算法是在前期BW AS算法優(yōu)化研究基礎(chǔ)之上開(kāi)展的無(wú)線傳感器網(wǎng)絡(luò)的路由研究，但在概率分簇和路由算法設(shè)計(jì)時(shí)是基于血管路徑特性。對(duì)于傳感器節(jié)點(diǎn)數(shù)量較大的網(wǎng)絡(luò)，此算法在能效均衡和容錯(cuò)穩(wěn)定等方面具有較好的性能，這在實(shí)際應(yīng)用中具有重要的意義。作為一種新穎的路由算法，在理論分析、體系完善并得到實(shí)際應(yīng)用的過(guò)程中還有諸多方面值得深入研究，如在不同情況下等級(jí)分簇的能效性判定、數(shù)據(jù)傳輸?shù)挠行砸约皵?shù)據(jù)傳輸工作機(jī)制等。

［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］劉志，裘正定.基于分環(huán)多跳的無(wú)線傳感網(wǎng)分簇路由算法［J］.通信學(xué)報(bào)，2008，29（3）：104－113.

LIU Zhi，QIU Zheng－ding.Ring based multi－h(huán)op 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］李洪兵，余成波，陳強(qiáng)，等.基于BW AS的無(wú)線傳感器網(wǎng)絡(luò)靜態(tài)分簇路由算法［J］.電訊技術(shù)，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－），男，博士，教授，重慶理工大學(xué)碩士生導(dǎo)師，中北大學(xué)博士生導(dǎo)師，重慶市學(xué)術(shù)技術(shù)帶頭人。主要研究領(lǐng)域?yàn)樾畔@取與處理技術(shù)、遠(yuǎn)程測(cè)試與控制技術(shù)和車輛電子技術(shù)；

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－），女，重慶潼南人，碩士研究生，講師，主要研究方向?yàn)樾盘?hào)處理、虛擬儀器軟件開(kāi)發(fā)；

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－），男，江蘇儀征人，碩士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

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－），男，重慶潼南人，碩士研究生，講師，主要研究方向?yàn)橹悄苄盘?hào)處理、無(wú)線傳感器網(wǎng)絡(luò)；

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

2010－10－21；

2010－12－08

重慶市自然科學(xué)基金重點(diǎn)項(xiàng)目（CSTC2007BA2023）；重慶市九龍坡科技計(jì)劃項(xiàng)目（九龍坡科委發(fā)［2009］52號(hào)）；重慶市科技創(chuàng)新項(xiàng)目（渝經(jīng)信科技［2010］9號(hào)）；重慶市萬(wàn)州科技計(jì)劃項(xiàng)目（萬(wàn)州科委［2010］23號(hào)）