基于節(jié)點(diǎn)綜合故障模型的無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)拓?fù)淇刂品椒?/h1>
2012-07-25 04:08:40尹榮榮劉浩然郝曉辰
電子與信息學(xué)報(bào) 2012年10期
尹榮榮 劉 彬 劉浩然 郝曉辰
(燕山大學(xué)電氣工程學(xué)院 秦皇島 066004)
1 引言
無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)可以隨時(shí)隨地自組成網(wǎng)，特別適合在敵對(duì)或惡劣條件下快速組網(wǎng)，形成對(duì)特定目標(biāo)的有效監(jiān)視[1]。由于傳感器節(jié)點(diǎn)常部署在面積廣大且人跡罕至甚至危險(xiǎn)的遠(yuǎn)程環(huán)境中，供電電池不易替換[2]，環(huán)境損壞造成的節(jié)點(diǎn)失效情況頻繁出現(xiàn)[3]，所以綜合關(guān)注網(wǎng)絡(luò)節(jié)能效率和節(jié)點(diǎn)隨機(jī)故障容忍能力的容錯(cuò)拓?fù)淇刂芠4]是WSNs的一個(gè)重要研究課題。
目前容錯(cuò)拓?fù)淇刂频难芯?，重點(diǎn)集中于探索分布式算法構(gòu)造具有節(jié)能特點(diǎn)的k連通容錯(cuò)網(wǎng)絡(luò)[5]與無(wú)標(biāo)度容錯(cuò)網(wǎng)絡(luò)[6]，以保證節(jié)點(diǎn)隨機(jī)失效下的網(wǎng)絡(luò)正常運(yùn)行。對(duì)于k連通容錯(cuò)算法，文獻(xiàn)[7]為冗余機(jī)制能自動(dòng)產(chǎn)生一個(gè)具備相似功能的替代方案，使網(wǎng)絡(luò)在任意k.-1個(gè)節(jié)點(diǎn)同時(shí)失效狀態(tài)下依然能正常工作，提出了k連通k支配集構(gòu)造算法；文獻(xiàn)[8]認(rèn)為在連通支配集中節(jié)點(diǎn)存在功能差異，配備相同的冗余度并非必要，拓展了基于睡眠/工作調(diào)度的k連通m支配集生成算法；文獻(xiàn)[9]聯(lián)合睡眠調(diào)度和功率調(diào)整技術(shù)，給出了簇間k連通容錯(cuò)拓?fù)淇刂扑惴?；這些算法均為WSNs建立了k連通最小能耗容錯(cuò)拓?fù)?，但是，網(wǎng)絡(luò)維持k連通需要耗費(fèi)大量的能量資源[10]，造成僅能容忍少量隨機(jī)失效節(jié)點(diǎn)的弊端。因此，近來少量學(xué)者從無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)隨機(jī)失效的強(qiáng)容錯(cuò)性[11,12]出發(fā)，建立適用于WSNs的無(wú)標(biāo)度拓?fù)浣Y(jié)構(gòu)。如，陳力軍等人[13]借助隨機(jī)行走機(jī)制，通過改善拓?fù)渚鶆蛐?，生成了具有無(wú)標(biāo)度特征的WSNs簇間拓?fù)浣Y(jié)構(gòu)；文獻(xiàn)[14]將節(jié)點(diǎn)剩余能量與無(wú)標(biāo)度網(wǎng)絡(luò)擇優(yōu)增長(zhǎng)機(jī)制相結(jié)合，建立了具有無(wú)標(biāo)度特征的 WSNs能量均衡拓?fù)洌晃墨I(xiàn)[15]借助適應(yīng)度拓?fù)溲莼Ｐ?，將適應(yīng)度計(jì)算與節(jié)點(diǎn)能量值直接關(guān)聯(lián)，提出了WSNs無(wú)標(biāo)度拓?fù)錁?gòu)建算法；他們均使WSNs具有了無(wú)標(biāo)度網(wǎng)絡(luò)的強(qiáng)容錯(cuò)性。然而，無(wú)論是k連通構(gòu)建算法還是無(wú)標(biāo)度生成算法，皆是在保證網(wǎng)絡(luò)容錯(cuò)結(jié)構(gòu)基礎(chǔ)上進(jìn)行的能量?jī)?yōu)化，由于忽視了節(jié)點(diǎn)能量耗盡故障對(duì)拓?fù)淙蒎e(cuò)性的影響，導(dǎo)致建立的網(wǎng)絡(luò)拓?fù)淙蒎e(cuò)性差，而且存在嚴(yán)重的能效約束。因此，面向節(jié)點(diǎn)能量耗盡和隨機(jī)失效的綜合故障優(yōu)化是探索更加有效的WSNs容錯(cuò)拓?fù)淇刂品椒ǖ男滤悸贰?/p>
基于上述分析，本文提出一種基于節(jié)點(diǎn)能量耗盡和隨機(jī)失效綜合故障模型的WSNs容錯(cuò)拓?fù)淇刂品椒?FTCA(Fault-tolerant Topology Control Approach)，該方法首先根據(jù)節(jié)點(diǎn)能量耗盡和隨機(jī)失效信息進(jìn)行綜合故障建模，然后利用不等式放縮法與一元函數(shù)極值分析法對(duì)故障模型進(jìn)行節(jié)點(diǎn)度量化分析，最后通過調(diào)整網(wǎng)絡(luò)中各節(jié)點(diǎn)的節(jié)點(diǎn)度趨于其節(jié)點(diǎn)度最優(yōu)值對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行控制，保證了網(wǎng)絡(luò)生命期和節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合容忍能力的雙重需求。
2 節(jié)點(diǎn)綜合故障建模
由于能量耗盡造成節(jié)點(diǎn)故障和環(huán)境損壞導(dǎo)致節(jié)點(diǎn)隨機(jī)失效是WSNs故障的主要表現(xiàn)形式，則可將網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的故障概率表示為能量耗盡概率fe(i)和隨機(jī)失效概率fr(i)的乘積形式。
其中fe(i)[16]取決于節(jié)點(diǎn)i的初始能量E0(i)，能量消耗Ec(i)和網(wǎng)絡(luò)運(yùn)行時(shí)間t，即
采用圖 1無(wú)線通信能耗模型[17]，相距為d的節(jié)點(diǎn)發(fā)送lbit數(shù)據(jù)所消耗的能量Etx為信號(hào)發(fā)射電路與信號(hào)放大電路消耗的能量之和為
節(jié)點(diǎn)接收l(shuí)bit數(shù)據(jù)消耗能量Erx由式(4)計(jì)算得到
那么，節(jié)點(diǎn)i的總能耗Ec(i)可用下述形式表示：
假設(shè)N個(gè)節(jié)點(diǎn)均勻散布在 2維有界監(jiān)測(cè)區(qū)域G(面積為A)內(nèi)，則節(jié)點(diǎn)落入以通信距離d為半徑的圓域D內(nèi)的概率為
圖1 無(wú)線通信能耗模型
即節(jié)點(diǎn)傳輸距離d與其節(jié)點(diǎn)度k之間存在如下關(guān)系：
將式(7)代入式(5)可得節(jié)點(diǎn)i的能耗值Ec(i)隨其節(jié)點(diǎn)度k的變化關(guān)系，進(jìn)而代入式(2)得到由節(jié)點(diǎn)度k和運(yùn)行時(shí)間t描述的節(jié)點(diǎn)能量耗盡概率fe(i)。
考慮到節(jié)點(diǎn)隨機(jī)失效是因環(huán)境損壞導(dǎo)致網(wǎng)絡(luò)稀疏，從而使節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行環(huán)境中發(fā)生孤立喪失規(guī)定功能的一類故障，其概率與節(jié)點(diǎn)度k呈指數(shù)變化關(guān)系[18]，有
結(jié)合式(1)、式(8)和式(9)，可得網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的故障模型如下：
從而，利用節(jié)點(diǎn)度k和網(wǎng)絡(luò)運(yùn)行時(shí)間t，節(jié)點(diǎn)能量耗盡和環(huán)境損壞造成的綜合失效故障具有式(10)的統(tǒng)一模型形式，有必要對(duì)k值進(jìn)行分析，以得到WSNs容錯(cuò)拓?fù)錁?gòu)建的理論依據(jù)。
3 基于故障模型的節(jié)點(diǎn)度量化分析
在對(duì)k值進(jìn)行量化分析之前，必須對(duì)網(wǎng)絡(luò)生命期和節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合故障容忍能力的雙重需求進(jìn)行定義：
討論定義1是針對(duì)網(wǎng)絡(luò)拓?fù)涞墓?jié)能和容錯(cuò)雙重需求而言的，此定義表明，對(duì)于一個(gè)網(wǎng)絡(luò)G，為提高其拓?fù)涞哪芰坑行裕W(wǎng)絡(luò)G須保證一定的生存時(shí)間tmin，即t≥tmin；同時(shí)為增強(qiáng)其拓?fù)鋵?duì)隨機(jī)失效節(jié)點(diǎn)的容忍能力，網(wǎng)絡(luò)G須維持一定的節(jié)點(diǎn)度下限kmin，即k≥kmin，而為增強(qiáng)其拓?fù)鋵?duì)能量耗盡節(jié)點(diǎn)的容錯(cuò)性，網(wǎng)絡(luò)G又須限定其節(jié)點(diǎn)度的上限kmax，即k≤kmax。可見，若網(wǎng)絡(luò)G滿足定義 1的條件，則它不僅可以確保網(wǎng)絡(luò)的生存時(shí)間需求，又可以增強(qiáng)容忍能量耗盡和環(huán)境損壞導(dǎo)致的綜合節(jié)點(diǎn)失效現(xiàn)象，也就是說，能夠滿足網(wǎng)絡(luò)生命期和綜合故障容忍能力要求較高的應(yīng)用場(chǎng)景。
3.1 滿足雙重需求的節(jié)點(diǎn)故障率分析
基于節(jié)點(diǎn)故障模型(式(10))和網(wǎng)絡(luò)生命期及綜合故障容忍能力雙重需求(定義1)，給出滿足網(wǎng)絡(luò)生命期和綜合故障容忍能力雙重需求的節(jié)點(diǎn)故障率取值。
證明為確保網(wǎng)絡(luò)滿足定義 1，網(wǎng)絡(luò)中任意節(jié)點(diǎn)i須滿足定義1，為此下面采用不等式放縮法對(duì)滿足定義1的節(jié)點(diǎn)故障率f(i)進(jìn)行討論。
(1)由t≥tmin可得，節(jié)點(diǎn)i的故障率f(i)符合
又根據(jù)kmin≤k≤kmax易得
那么由不等式的基本性質(zhì)可以推出
(2)由kmin≤k≤kmax得
基于不等式的基本性質(zhì)，由式(10)得到
綜合式(14)和式(17)，有
3.2 節(jié)點(diǎn)度的定量分析
根據(jù)定理 1，網(wǎng)絡(luò)生命期和綜合故障容忍能力的雙重需求轉(zhuǎn)化成了節(jié)點(diǎn)故障率的要求(式(18))，在此基礎(chǔ)上，通過一元函數(shù)極值分析法可以對(duì)節(jié)點(diǎn)度進(jìn)行定量分析，獲取在滿足故障率要求下具有最大生存時(shí)間的節(jié)點(diǎn)度取值，為網(wǎng)絡(luò)拓?fù)錁?gòu)建提供依據(jù)。
證明令c=a/b，當(dāng)節(jié)點(diǎn)故障率滿足f(i) =f0，記網(wǎng)絡(luò)運(yùn)行時(shí)間t為，根據(jù)式(10)有
采用一元函數(shù)極值分析法研究節(jié)點(diǎn)度取值k與網(wǎng)絡(luò)生存時(shí)間之間的變化關(guān)系，對(duì)關(guān)于k求一階導(dǎo)數(shù)得
進(jìn)而，根據(jù)式(20)可得，在k∈[kmin,+ ∞) 內(nèi)＞0，那么是增函數(shù)，從而，在滿足k≤kmax且e-k-f0＞ 0 的條件下，即k=min{kmax,- lnf0}點(diǎn)處，最大。也就是說，存在唯一極值點(diǎn)k0=min{kmax,- lnf0}，使得節(jié)點(diǎn)i在滿足故障率要求下可實(shí)現(xiàn)其生命期的最大化。 證畢
綜上，本節(jié)獲得了滿足網(wǎng)絡(luò)生命期和綜合故障容忍能力雙重需求的節(jié)點(diǎn)度k的最優(yōu)值k0，為構(gòu)建可最大限度延長(zhǎng)網(wǎng)絡(luò)生命期，且能夠有效提高對(duì)節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合故障容忍能力的目標(biāo)拓?fù)涮峁┮罁?jù)。
4 基于節(jié)點(diǎn)度調(diào)整的FTCA算法
FTCA算法是基于確定的節(jié)點(diǎn)度最優(yōu)值k0提出的一種WSNs容錯(cuò)拓?fù)淇刂品椒?，主要包括以下步驟：
(1)信息交換 各節(jié)點(diǎn)以最大發(fā)射功率廣播包含自身id和位置信息(x,y)的HELLO數(shù)據(jù)包。任意收到HELLO包的節(jié)點(diǎn)建立其鄰居列表，以節(jié)點(diǎn)i為例，鄰居列表nl(i)的表頭格式如表1所示。其中，id(j)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j的id,(xj,yj)表示節(jié)點(diǎn)j的地理位置，d(i,j)為i和j之間的距離，由兩點(diǎn)間的距離公式計(jì)算得到，mark(j)為狀態(tài)標(biāo)識(shí)，初始記為0。
表1 節(jié)點(diǎn)i鄰居列表nl( i)的表頭格式
(2)鄰居排序 節(jié)點(diǎn)i依據(jù)鄰居列表nl(i)中距離的升序排列其鄰節(jié)點(diǎn)，并廣播包含自身id和鄰居列表的NOTICE信息。對(duì)于收到NOTICE信息的節(jié)點(diǎn)，判斷自身通信區(qū)域內(nèi)的鏈路狀態(tài)，建立區(qū)域鏈路列表，其表頭格式見表2。其中，d(j1,j2)為節(jié)點(diǎn)i的相互可達(dá)鄰居節(jié)點(diǎn)j1和j2間的距離，id(j1)和id(j2) 分別為j1,j2的id, s ign(j1,j2)為狀態(tài)標(biāo)識(shí)，初始設(shè)定為0。
表2 節(jié)點(diǎn)i區(qū)域鏈路列表ll( i)的表頭格式
節(jié)點(diǎn)i按照通信距離d(j1,j2)對(duì)其區(qū)域鏈路列表ll(i)進(jìn)行升序排列，如果j1和j2之間不存在通信路徑，將鏈路l(j1,j2)的狀態(tài)標(biāo)識(shí)sign(ji,jj)更新為1，直至與所有鄰節(jié)點(diǎn)皆建立通信路徑為止，刪除sign標(biāo)記為0的鏈路項(xiàng)信息。
(3)鏈路選擇 基于區(qū)域鏈路列表ll(i)，節(jié)點(diǎn)i尋找ll(i)中由自身出發(fā)的鏈路項(xiàng)，將其sign標(biāo)記為2，刪除標(biāo)記為1的鏈路項(xiàng)信息，并廣播包含自身id和ll(i)信息的CONNECT數(shù)據(jù)包。根據(jù)所接收到的CONNECT數(shù)據(jù)，以鏈路雙向性原則確定其鄰節(jié)點(diǎn)，并將其nl列表中的相應(yīng)標(biāo)識(shí)位mark更新為1，統(tǒng)計(jì)其數(shù)目記為kmin，計(jì)算出k0與kmin的差值。按距離升序依次將個(gè)nl列表中標(biāo)識(shí)為0的節(jié)點(diǎn)標(biāo)記為2，廣播其id，保留具有雙向鏈路的鄰節(jié)點(diǎn)，將nl中相應(yīng)狀態(tài)標(biāo)識(shí)更新為 1，刪除狀態(tài)不為 1的鄰節(jié)點(diǎn)信息項(xiàng)。
(4)功率調(diào)整 最后，節(jié)點(diǎn)i確定的發(fā)射功率應(yīng)保證與其所有鄰節(jié)點(diǎn)(位于已更新的鄰居列表nl中)皆能正常通信，即節(jié)點(diǎn)i的發(fā)射半徑為di=max{d(i,j)|j∈nl(i) } 。
5 實(shí)驗(yàn)分析
本文使用仿真工具 Matlab實(shí)現(xiàn)k連通算法k-Grid(k=2)[7]、無(wú)標(biāo)度算法 EAEM(m0=2,m=1)[14]以及FTCA算法，并比較所得網(wǎng)絡(luò)拓?fù)涞墓?jié)能性和容錯(cuò)能力。實(shí)驗(yàn)中參數(shù)設(shè)置如表3所示，運(yùn)行仿真實(shí)驗(yàn)50次，以下分析數(shù)據(jù)均為50次實(shí)驗(yàn)數(shù)據(jù)均值。
基于網(wǎng)絡(luò)生命期和節(jié)點(diǎn)能量耗盡故障及隨機(jī)失效故障綜合容忍能力的雙重需求，節(jié)點(diǎn)度k的量化分析結(jié)果如圖2所示，該圖直觀地描述并驗(yàn)證了k的最優(yōu)值k0的存在性。圖3描述了FTCA算法所得目標(biāo)拓?fù)渲泄?jié)點(diǎn)平均度＜k＞與其理論最優(yōu)值k0之間的偏差情況，偏差越小意味FTCA算法的準(zhǔn)確率越高。從圖2中可以看出，當(dāng)節(jié)點(diǎn)度取值為k=-ln(f0)時(shí)其生存時(shí)間t達(dá)到最大，即最優(yōu)值k0的存在性在圖中得到了很好的體現(xiàn)。從圖3中可以看出，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目增加時(shí)，F(xiàn)TCA算法所得拓?fù)涞墓?jié)點(diǎn)平均度與理論最優(yōu)值之間的偏差在減小，且最大偏差小于0.15，也就是說，F(xiàn)TCA算法可以有效保證生成拓?fù)涞臏?zhǔn)確性。
圖 4描述了原始拓?fù)浣Y(jié)構(gòu)Gs以及k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目標(biāo)拓?fù)浣Y(jié)構(gòu)圖，該圖驗(yàn)證了FTCA算法的相關(guān)拓?fù)湫再|(zhì)，如連通性、對(duì)稱性與魯棒性。從圖4可以看出，k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法均對(duì)原始拓?fù)浣Y(jié)構(gòu)Gs進(jìn)行了簡(jiǎn)化，生成的目標(biāo)拓?fù)浣Y(jié)構(gòu)都保留了雙向鏈路。另外，由于k-Grid(k=2)算法基于概率進(jìn)行拓?fù)錁?gòu)建，依據(jù)鏈路冗余實(shí)現(xiàn)拓?fù)淙蒎e(cuò)，較 EAEM(m0=2,m=1)算法和FTCA算法所得拓?fù)涓鼮槊芗?，且拓?fù)涞倪B通性不能很好地保證；而EAEM算法是根據(jù)結(jié)構(gòu)的不均勻性實(shí)現(xiàn)容錯(cuò)，F(xiàn)TCA算法是以維持各節(jié)點(diǎn)的節(jié)點(diǎn)度在某一特定值達(dá)到容錯(cuò)，兩者所得拓?fù)浣Y(jié)構(gòu)更為稀疏，且有效確保了所得拓?fù)涞娜B通。
表3 實(shí)驗(yàn)參數(shù)設(shè)置
圖2 節(jié)點(diǎn)度最優(yōu)值k0存在性分析圖
圖3 FTCA算法準(zhǔn)確性分析圖
圖4 拓?fù)浣Y(jié)構(gòu)分析圖
圖 5描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目標(biāo)拓?fù)涞墓?jié)點(diǎn)平均發(fā)射半徑。由于較小的發(fā)射半徑能夠降低節(jié)點(diǎn)能量消耗，減少通信干擾，增大網(wǎng)絡(luò)容量，因此節(jié)點(diǎn)的發(fā)射半徑大小一定程度上能體現(xiàn)網(wǎng)絡(luò)的節(jié)能性，是容錯(cuò)拓?fù)淇刂扑惴ㄗ非蟮牧己猛負(fù)湫再|(zhì)之一。圖 6描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法所得目標(biāo)拓?fù)涞墓?jié)點(diǎn)平均度。由于節(jié)點(diǎn)最小度為k的k連通網(wǎng)絡(luò)在任意k-1個(gè)節(jié)點(diǎn)失效后仍能保持連通，具有k-1的容錯(cuò)能力，雖然節(jié)點(diǎn)平均度為k不能保證網(wǎng)絡(luò)是k連通，但是，節(jié)點(diǎn)的平均度在一定程度上也能反映網(wǎng)絡(luò)的容錯(cuò)能力，是容錯(cuò)拓?fù)淇刂扑惴ㄗ非蟮挠忠涣己猛負(fù)湫再|(zhì)。從圖5可以看出，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)從100至500的變化中，由于FTCA算法所得拓?fù)錈o(wú)需維持k-Grid(k=2)拓?fù)涞娜哂噫溌?，也不存?EAEM(m0=2,m=1)拓?fù)涞募?度很大)節(jié)點(diǎn)，故其節(jié)點(diǎn)平均發(fā)射半徑始終遠(yuǎn)小于k-Grid(k=2)和EAEM(m0=2,m=1)拓?fù)洌⑶译S著節(jié)點(diǎn)數(shù)的增大，節(jié)點(diǎn)平均發(fā)射半徑逐漸減小，即網(wǎng)絡(luò)具有更好的節(jié)能性。從圖6可以看出，由于FTCA算法以節(jié)點(diǎn)能量故障和隨機(jī)故障的協(xié)同優(yōu)化為設(shè)計(jì)目標(biāo)，通過各節(jié)點(diǎn)維持某一特定節(jié)點(diǎn)度實(shí)現(xiàn)容錯(cuò)，所得拓?fù)涞墓?jié)點(diǎn)平均度低于k-Grid(k=2)冗余拓?fù)?，高?EAEM(m0=2,m=1)非冗余拓?fù)?，即網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)隨機(jī)失效的容忍能力介于k-Grid(k=2)拓?fù)渑cEAEM(m0=2,m=1)拓?fù)渲g。
WSNs生命期定義為有效數(shù)據(jù)采集輪數(shù)(采集1輪數(shù)據(jù)規(guī)定為全網(wǎng)中各節(jié)點(diǎn)傳輸數(shù)據(jù)1次)是評(píng)價(jià)容錯(cuò)拓?fù)淇刂扑惴ㄐ阅艿闹匾笜?biāo)，對(duì)于特定的節(jié)點(diǎn)數(shù)(100個(gè))，分別運(yùn)行k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA 算法，然后以 Poisson規(guī)則隨機(jī)地失效節(jié)點(diǎn)，直到可用節(jié)點(diǎn)(位于最大連通分支中)數(shù)占網(wǎng)絡(luò)原有節(jié)點(diǎn)數(shù)的50%時(shí)停止，此時(shí)網(wǎng)絡(luò)生命期也終止。圖7給出了上述算法所得目標(biāo)拓?fù)湓诠?jié)點(diǎn)能量耗盡與隨機(jī)失效故障共存下的生命期變化情況。其中，圖 7(a)描述了從開始至網(wǎng)絡(luò)終止整個(gè)運(yùn)行時(shí)間段內(nèi)的節(jié)點(diǎn)隨機(jī)失效現(xiàn)象，圖7(b)為該時(shí)間段內(nèi)網(wǎng)絡(luò)可用節(jié)點(diǎn)數(shù)的變化情況，圖 7(c)為網(wǎng)絡(luò)出現(xiàn)節(jié)點(diǎn)能量耗盡故障的運(yùn)行時(shí)刻，圖7(d)為網(wǎng)絡(luò)出現(xiàn)節(jié)點(diǎn)隨機(jī)失效故障的運(yùn)行時(shí)刻。可見，k-Grid(k=2)算法所得拓?fù)鋵?duì)隨機(jī)節(jié)點(diǎn)失效有較強(qiáng)的容錯(cuò)能力，在網(wǎng)絡(luò)終止前僅出現(xiàn)一次因隨機(jī)失效節(jié)點(diǎn)引發(fā)的網(wǎng)絡(luò)分割現(xiàn)象(圖 7(d))，但因多節(jié)點(diǎn)的能量耗盡故障(圖7(c))導(dǎo)致網(wǎng)絡(luò)較早終止(圖7(b))；EAEM(m0=2,m=1)算法所得網(wǎng)絡(luò)拓?fù)涞娜蒎e(cuò)能力恰與k-Grid(k=2)拓?fù)湎喾?，在網(wǎng)絡(luò)終止前沒有出現(xiàn)過節(jié)點(diǎn)能量耗盡現(xiàn)象(圖 7(c))，卻因部分隨機(jī)失效節(jié)點(diǎn)發(fā)生網(wǎng)絡(luò)分割(圖 7(d))，最終因集散節(jié)點(diǎn)的能量耗盡故障而較早終止運(yùn)行(圖 7(b))；FTCA算法由于考慮了節(jié)點(diǎn)能量耗盡故障對(duì)網(wǎng)絡(luò)容錯(cuò)性的影響，并以優(yōu)化節(jié)點(diǎn)綜合故障為設(shè)計(jì)目標(biāo)，所得拓?fù)浣Y(jié)構(gòu)在最大化網(wǎng)絡(luò)生命期(圖 7(b))和提升網(wǎng)絡(luò)綜合故障容忍能力方面(圖 7(c)和圖 7(d))均體現(xiàn)出極佳的效果，大大延長(zhǎng)了網(wǎng)絡(luò)的生命期，增強(qiáng)了網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)能量耗盡故障和隨機(jī)失效故障的綜合容錯(cuò)性。
圖5 節(jié)點(diǎn)平均發(fā)射半徑分析圖
圖6 節(jié)點(diǎn)平均度分析圖
圖7 節(jié)點(diǎn)能量耗盡與隨機(jī)失效綜合故障下網(wǎng)絡(luò)生命期分析圖
6 結(jié)束語(yǔ)
本文提出了一種基于節(jié)點(diǎn)能量耗盡和隨機(jī)失效綜合故障模型的WSNs容錯(cuò)拓?fù)淇刂品椒‵TCA，使得生成的網(wǎng)絡(luò)拓?fù)渚哂休^大生命期和對(duì)節(jié)點(diǎn)能量耗盡及隨機(jī)失效強(qiáng)容錯(cuò)的雙重性能。另外，通過對(duì)節(jié)點(diǎn)故障模型的分析得出，當(dāng)節(jié)點(diǎn)度為 min{kmax,- ln (f0)}時(shí)可以獲得滿足節(jié)能和容錯(cuò)雙重需求的目標(biāo)拓?fù)?；并?duì)FTCA算法實(shí)驗(yàn)數(shù)據(jù)的分析得出，相對(duì)k-Grid(k=2)算法和 EAEM(m0=2,m=1)算法，F(xiàn)TCA算法由于采用了節(jié)點(diǎn)能量故障和隨機(jī)故障綜合優(yōu)化的節(jié)點(diǎn)度取值，大大延緩了因節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合故障造成的網(wǎng)絡(luò)生命期終止時(shí)刻，有效地增強(qiáng)了網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)能量耗盡及隨機(jī)失效的綜合容錯(cuò)能力。
[1]Akyildiz I F, Su W, Sankarasubramaniam Y,et al.. Wireless sensor networks: a survey[J].Computer Networks, 2002, 38(4):393-422.
[2]Chen I R, Speer A P, and Eltoweissy M. Adaptive fault-tolerant QoS control algorithm for maximizing system lifetime of query-based wireless sensor networks[J].IEEE Transactions on Dependable and Secure Computing, 2011,8(2): 161-176.
[3]Lee S and Younis M. Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J].Journal of Parallel and Distributed Computing, 2010,70(5): 525-536.
[4]Bari A, Jaekel A, Jiang J,et al.. Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirement[J].Computer Communications, 2012, 35(3):320-333.
[5]Zhang W Y, Xue G L, and Misra S. Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms[C]. Proceedings-IEEE INFOCOM, Anchorage,AK, 2007: 1649-1657.
[6]Zhang K, Han D H, and Feng H P. A model of linear expanding in the local-world based on the laws of internal evolution of the wireless sensor networks[C]. Proceedings of the 2010 International Conference on Computer Application and System Modeling, Taiyuan, China, 2010: 357-360.
[7]Dai F and Wu J. On constructing k-connected k-dominating set in wireless Ad hoc and sensor networks[J].Journal of Parallel and Distributed Computing, 2006, 66(7): 947-958.
[8]Zhao Y X, Wu J, Li F,et al.. VBS: maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones[C]. Proceedings-IEEE INFOCOM, San Diego, CA,2010: 1-5.
[9]Forghani A and Rahmani A M. Multi state fault tolerant topology control algorithm for wireless sensor networks[C].Proceedings of the 2008 2nd International Conference on Future Generation Communication and Networking, Hainan Island, China, 2008: 433-436.
[10]王良民, 馬建峰, 王超. 無(wú)線傳感器網(wǎng)絡(luò)拓?fù)涞娜蒎e(cuò)度與容侵度[J]. 電子學(xué)報(bào), 2006, 34(8): 1446-1451.
Wang L M, Ma J F, and Wang C. Degree of fault-tolerance and intrusion-tolerance for topologies of wireless sensor networks[J].Acta Electronic Sinica, 2006, 34(8): 1446-1451.
[11]Barabasi A L and Albert R. Emergence of scaling in random networks[J].Science, 1999, 286(5439): 509-512.
[12]Cohen R, Erez K, Ben A D,et al.. Resilience of the internet to random breakdowns[J].Physical Review Letters, 2000, 85(21):4626-4628.
[13]陳力軍, 劉明, 陳道蓄, 等. 基于隨機(jī)行走的無(wú)線傳感器網(wǎng)絡(luò)簇間拓?fù)溲莼痆J]. 計(jì)算機(jī)學(xué)報(bào), 2009, 32(1): 69-76.
Chen L J, Liu M, Chen D X,et al.. Topology evolution of wireless sensor networks among cluster heads by random walkers[J].Chinese Journal of Computers, 2009, 32(1): 69-76.
[14]Zhu H L, Luo H, Peng H P,et al.. Complex networks-based energy-efficient evolution model for wireless sensor networks[J].Chaos,Solitons and Fractals, 2009, 41(4):1828-1835.
[15]Qi X Q, Ma S Q, and Zheng G Z. Topology evolution of wireless sensor networks based on adaptive free-scale networks[J].Journal of Information and Computational Science, 2011, 8(3): 467-475.
[16]Mizanian K, Yousefi H, and Jahangir A H. Modeling and evaluating reliable real-time degree in multi-hop wireless sensor networks[C]. Proceedings of the 2009 IEEE Sarnoff Symposium, Princeton, NJ, 2009: 1-6.
[17]Heizelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. Proceedings of the Hawaii International Conference on System Sciences, Maui, USA,2000: 1-10.
[18]Kleinrock L and Silvester J. Optimum transmission radii for packet radio networks or why six is a magic number[C].Proceedings of the National Telecommunications Conference,Birmingham Ala, 1978: 1-5.
猜你喜歡
巧用列表來推理小學(xué)生學(xué)習(xí)指導(dǎo)(高年級(jí))(2024年4期)2024-05-07 03:28:46 層次分析法中兩種標(biāo)度的對(duì)比分析玉溪師范學(xué)院學(xué)報(bào)(2023年3期)2023-08-31 14:11:56 學(xué)習(xí)運(yùn)用列表法小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2021年4期)2021-04-27 10:14:56 擴(kuò)列吧課堂內(nèi)外(初中版)(2020年5期)2020-06-19 08:11:11 冬季歐亞大陸反氣旋活動(dòng)特征及其與中國(guó)氣溫的關(guān)系大氣科學(xué)學(xué)報(bào)(2017年3期)2017-05-30 10:48:04 加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)上SIRS 類傳播模型研究河北工業(yè)大學(xué)學(xué)報(bào)(2016年6期)2016-04-16 02:54:19 飛行試驗(yàn)項(xiàng)目生命期研究項(xiàng)目管理技術(shù)(2015年10期)2015-12-26 09:36:04 無(wú)線傳感器網(wǎng)絡(luò)最大生命期聚合樹路由算法*傳感器與微系統(tǒng)(2014年1期)2014-09-20 08:03:28 不含3-圈的1-平面圖的列表邊染色與列表全染色華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2014年3期)2014-03-11 16:18:15 創(chuàng)新孵化網(wǎng)絡(luò)演化無(wú)標(biāo)度特征仿真分析技術(shù)經(jīng)濟(jì)(2014年10期)2014-02-28 01:30:01
尹榮榮 劉 彬 劉浩然 郝曉辰
(燕山大學(xué)電氣工程學(xué)院 秦皇島 066004)
1 引言
無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)可以隨時(shí)隨地自組成網(wǎng)，特別適合在敵對(duì)或惡劣條件下快速組網(wǎng)，形成對(duì)特定目標(biāo)的有效監(jiān)視[1]。由于傳感器節(jié)點(diǎn)常部署在面積廣大且人跡罕至甚至危險(xiǎn)的遠(yuǎn)程環(huán)境中，供電電池不易替換[2]，環(huán)境損壞造成的節(jié)點(diǎn)失效情況頻繁出現(xiàn)[3]，所以綜合關(guān)注網(wǎng)絡(luò)節(jié)能效率和節(jié)點(diǎn)隨機(jī)故障容忍能力的容錯(cuò)拓?fù)淇刂芠4]是WSNs的一個(gè)重要研究課題。
目前容錯(cuò)拓?fù)淇刂频难芯?，重點(diǎn)集中于探索分布式算法構(gòu)造具有節(jié)能特點(diǎn)的k連通容錯(cuò)網(wǎng)絡(luò)[5]與無(wú)標(biāo)度容錯(cuò)網(wǎng)絡(luò)[6]，以保證節(jié)點(diǎn)隨機(jī)失效下的網(wǎng)絡(luò)正常運(yùn)行。對(duì)于k連通容錯(cuò)算法，文獻(xiàn)[7]為冗余機(jī)制能自動(dòng)產(chǎn)生一個(gè)具備相似功能的替代方案，使網(wǎng)絡(luò)在任意k.-1個(gè)節(jié)點(diǎn)同時(shí)失效狀態(tài)下依然能正常工作，提出了k連通k支配集構(gòu)造算法；文獻(xiàn)[8]認(rèn)為在連通支配集中節(jié)點(diǎn)存在功能差異，配備相同的冗余度并非必要，拓展了基于睡眠/工作調(diào)度的k連通m支配集生成算法；文獻(xiàn)[9]聯(lián)合睡眠調(diào)度和功率調(diào)整技術(shù)，給出了簇間k連通容錯(cuò)拓?fù)淇刂扑惴?；這些算法均為WSNs建立了k連通最小能耗容錯(cuò)拓?fù)?，但是，網(wǎng)絡(luò)維持k連通需要耗費(fèi)大量的能量資源[10]，造成僅能容忍少量隨機(jī)失效節(jié)點(diǎn)的弊端。因此，近來少量學(xué)者從無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)隨機(jī)失效的強(qiáng)容錯(cuò)性[11,12]出發(fā)，建立適用于WSNs的無(wú)標(biāo)度拓?fù)浣Y(jié)構(gòu)。如，陳力軍等人[13]借助隨機(jī)行走機(jī)制，通過改善拓?fù)渚鶆蛐?，生成了具有無(wú)標(biāo)度特征的WSNs簇間拓?fù)浣Y(jié)構(gòu)；文獻(xiàn)[14]將節(jié)點(diǎn)剩余能量與無(wú)標(biāo)度網(wǎng)絡(luò)擇優(yōu)增長(zhǎng)機(jī)制相結(jié)合，建立了具有無(wú)標(biāo)度特征的 WSNs能量均衡拓?fù)洌晃墨I(xiàn)[15]借助適應(yīng)度拓?fù)溲莼Ｐ?，將適應(yīng)度計(jì)算與節(jié)點(diǎn)能量值直接關(guān)聯(lián)，提出了WSNs無(wú)標(biāo)度拓?fù)錁?gòu)建算法；他們均使WSNs具有了無(wú)標(biāo)度網(wǎng)絡(luò)的強(qiáng)容錯(cuò)性。然而，無(wú)論是k連通構(gòu)建算法還是無(wú)標(biāo)度生成算法，皆是在保證網(wǎng)絡(luò)容錯(cuò)結(jié)構(gòu)基礎(chǔ)上進(jìn)行的能量?jī)?yōu)化，由于忽視了節(jié)點(diǎn)能量耗盡故障對(duì)拓?fù)淙蒎e(cuò)性的影響，導(dǎo)致建立的網(wǎng)絡(luò)拓?fù)淙蒎e(cuò)性差，而且存在嚴(yán)重的能效約束。因此，面向節(jié)點(diǎn)能量耗盡和隨機(jī)失效的綜合故障優(yōu)化是探索更加有效的WSNs容錯(cuò)拓?fù)淇刂品椒ǖ男滤悸贰?/p>
基于上述分析，本文提出一種基于節(jié)點(diǎn)能量耗盡和隨機(jī)失效綜合故障模型的WSNs容錯(cuò)拓?fù)淇刂品椒?FTCA(Fault-tolerant Topology Control Approach)，該方法首先根據(jù)節(jié)點(diǎn)能量耗盡和隨機(jī)失效信息進(jìn)行綜合故障建模，然后利用不等式放縮法與一元函數(shù)極值分析法對(duì)故障模型進(jìn)行節(jié)點(diǎn)度量化分析，最后通過調(diào)整網(wǎng)絡(luò)中各節(jié)點(diǎn)的節(jié)點(diǎn)度趨于其節(jié)點(diǎn)度最優(yōu)值對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行控制，保證了網(wǎng)絡(luò)生命期和節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合容忍能力的雙重需求。
2 節(jié)點(diǎn)綜合故障建模
由于能量耗盡造成節(jié)點(diǎn)故障和環(huán)境損壞導(dǎo)致節(jié)點(diǎn)隨機(jī)失效是WSNs故障的主要表現(xiàn)形式，則可將網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的故障概率表示為能量耗盡概率fe(i)和隨機(jī)失效概率fr(i)的乘積形式。
其中fe(i)[16]取決于節(jié)點(diǎn)i的初始能量E0(i)，能量消耗Ec(i)和網(wǎng)絡(luò)運(yùn)行時(shí)間t，即
采用圖 1無(wú)線通信能耗模型[17]，相距為d的節(jié)點(diǎn)發(fā)送lbit數(shù)據(jù)所消耗的能量Etx為信號(hào)發(fā)射電路與信號(hào)放大電路消耗的能量之和為
節(jié)點(diǎn)接收l(shuí)bit數(shù)據(jù)消耗能量Erx由式(4)計(jì)算得到
那么，節(jié)點(diǎn)i的總能耗Ec(i)可用下述形式表示：
假設(shè)N個(gè)節(jié)點(diǎn)均勻散布在 2維有界監(jiān)測(cè)區(qū)域G(面積為A)內(nèi)，則節(jié)點(diǎn)落入以通信距離d為半徑的圓域D內(nèi)的概率為
圖1 無(wú)線通信能耗模型
即節(jié)點(diǎn)傳輸距離d與其節(jié)點(diǎn)度k之間存在如下關(guān)系：
將式(7)代入式(5)可得節(jié)點(diǎn)i的能耗值Ec(i)隨其節(jié)點(diǎn)度k的變化關(guān)系，進(jìn)而代入式(2)得到由節(jié)點(diǎn)度k和運(yùn)行時(shí)間t描述的節(jié)點(diǎn)能量耗盡概率fe(i)。
考慮到節(jié)點(diǎn)隨機(jī)失效是因環(huán)境損壞導(dǎo)致網(wǎng)絡(luò)稀疏，從而使節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行環(huán)境中發(fā)生孤立喪失規(guī)定功能的一類故障，其概率與節(jié)點(diǎn)度k呈指數(shù)變化關(guān)系[18]，有
結(jié)合式(1)、式(8)和式(9)，可得網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的故障模型如下：
從而，利用節(jié)點(diǎn)度k和網(wǎng)絡(luò)運(yùn)行時(shí)間t，節(jié)點(diǎn)能量耗盡和環(huán)境損壞造成的綜合失效故障具有式(10)的統(tǒng)一模型形式，有必要對(duì)k值進(jìn)行分析，以得到WSNs容錯(cuò)拓?fù)錁?gòu)建的理論依據(jù)。
3 基于故障模型的節(jié)點(diǎn)度量化分析
在對(duì)k值進(jìn)行量化分析之前，必須對(duì)網(wǎng)絡(luò)生命期和節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合故障容忍能力的雙重需求進(jìn)行定義：
討論定義1是針對(duì)網(wǎng)絡(luò)拓?fù)涞墓?jié)能和容錯(cuò)雙重需求而言的，此定義表明，對(duì)于一個(gè)網(wǎng)絡(luò)G，為提高其拓?fù)涞哪芰坑行裕W(wǎng)絡(luò)G須保證一定的生存時(shí)間tmin，即t≥tmin；同時(shí)為增強(qiáng)其拓?fù)鋵?duì)隨機(jī)失效節(jié)點(diǎn)的容忍能力，網(wǎng)絡(luò)G須維持一定的節(jié)點(diǎn)度下限kmin，即k≥kmin，而為增強(qiáng)其拓?fù)鋵?duì)能量耗盡節(jié)點(diǎn)的容錯(cuò)性，網(wǎng)絡(luò)G又須限定其節(jié)點(diǎn)度的上限kmax，即k≤kmax。可見，若網(wǎng)絡(luò)G滿足定義 1的條件，則它不僅可以確保網(wǎng)絡(luò)的生存時(shí)間需求，又可以增強(qiáng)容忍能量耗盡和環(huán)境損壞導(dǎo)致的綜合節(jié)點(diǎn)失效現(xiàn)象，也就是說，能夠滿足網(wǎng)絡(luò)生命期和綜合故障容忍能力要求較高的應(yīng)用場(chǎng)景。
3.1 滿足雙重需求的節(jié)點(diǎn)故障率分析
基于節(jié)點(diǎn)故障模型(式(10))和網(wǎng)絡(luò)生命期及綜合故障容忍能力雙重需求(定義1)，給出滿足網(wǎng)絡(luò)生命期和綜合故障容忍能力雙重需求的節(jié)點(diǎn)故障率取值。
證明為確保網(wǎng)絡(luò)滿足定義 1，網(wǎng)絡(luò)中任意節(jié)點(diǎn)i須滿足定義1，為此下面采用不等式放縮法對(duì)滿足定義1的節(jié)點(diǎn)故障率f(i)進(jìn)行討論。
(1)由t≥tmin可得，節(jié)點(diǎn)i的故障率f(i)符合
又根據(jù)kmin≤k≤kmax易得
那么由不等式的基本性質(zhì)可以推出
(2)由kmin≤k≤kmax得
基于不等式的基本性質(zhì)，由式(10)得到
綜合式(14)和式(17)，有
3.2 節(jié)點(diǎn)度的定量分析
根據(jù)定理 1，網(wǎng)絡(luò)生命期和綜合故障容忍能力的雙重需求轉(zhuǎn)化成了節(jié)點(diǎn)故障率的要求(式(18))，在此基礎(chǔ)上，通過一元函數(shù)極值分析法可以對(duì)節(jié)點(diǎn)度進(jìn)行定量分析，獲取在滿足故障率要求下具有最大生存時(shí)間的節(jié)點(diǎn)度取值，為網(wǎng)絡(luò)拓?fù)錁?gòu)建提供依據(jù)。
證明令c=a/b，當(dāng)節(jié)點(diǎn)故障率滿足f(i) =f0，記網(wǎng)絡(luò)運(yùn)行時(shí)間t為，根據(jù)式(10)有
采用一元函數(shù)極值分析法研究節(jié)點(diǎn)度取值k與網(wǎng)絡(luò)生存時(shí)間之間的變化關(guān)系，對(duì)關(guān)于k求一階導(dǎo)數(shù)得
進(jìn)而，根據(jù)式(20)可得，在k∈[kmin,+ ∞) 內(nèi)＞0，那么是增函數(shù)，從而，在滿足k≤kmax且e-k-f0＞ 0 的條件下，即k=min{kmax,- lnf0}點(diǎn)處，最大。也就是說，存在唯一極值點(diǎn)k0=min{kmax,- lnf0}，使得節(jié)點(diǎn)i在滿足故障率要求下可實(shí)現(xiàn)其生命期的最大化。 證畢
綜上，本節(jié)獲得了滿足網(wǎng)絡(luò)生命期和綜合故障容忍能力雙重需求的節(jié)點(diǎn)度k的最優(yōu)值k0，為構(gòu)建可最大限度延長(zhǎng)網(wǎng)絡(luò)生命期，且能夠有效提高對(duì)節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合故障容忍能力的目標(biāo)拓?fù)涮峁┮罁?jù)。
4 基于節(jié)點(diǎn)度調(diào)整的FTCA算法
FTCA算法是基于確定的節(jié)點(diǎn)度最優(yōu)值k0提出的一種WSNs容錯(cuò)拓?fù)淇刂品椒?，主要包括以下步驟：
(1)信息交換 各節(jié)點(diǎn)以最大發(fā)射功率廣播包含自身id和位置信息(x,y)的HELLO數(shù)據(jù)包。任意收到HELLO包的節(jié)點(diǎn)建立其鄰居列表，以節(jié)點(diǎn)i為例，鄰居列表nl(i)的表頭格式如表1所示。其中，id(j)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j的id,(xj,yj)表示節(jié)點(diǎn)j的地理位置，d(i,j)為i和j之間的距離，由兩點(diǎn)間的距離公式計(jì)算得到，mark(j)為狀態(tài)標(biāo)識(shí)，初始記為0。
表1 節(jié)點(diǎn)i鄰居列表nl( i)的表頭格式
(2)鄰居排序 節(jié)點(diǎn)i依據(jù)鄰居列表nl(i)中距離的升序排列其鄰節(jié)點(diǎn)，并廣播包含自身id和鄰居列表的NOTICE信息。對(duì)于收到NOTICE信息的節(jié)點(diǎn)，判斷自身通信區(qū)域內(nèi)的鏈路狀態(tài)，建立區(qū)域鏈路列表，其表頭格式見表2。其中，d(j1,j2)為節(jié)點(diǎn)i的相互可達(dá)鄰居節(jié)點(diǎn)j1和j2間的距離，id(j1)和id(j2) 分別為j1,j2的id, s ign(j1,j2)為狀態(tài)標(biāo)識(shí)，初始設(shè)定為0。
表2 節(jié)點(diǎn)i區(qū)域鏈路列表ll( i)的表頭格式
節(jié)點(diǎn)i按照通信距離d(j1,j2)對(duì)其區(qū)域鏈路列表ll(i)進(jìn)行升序排列，如果j1和j2之間不存在通信路徑，將鏈路l(j1,j2)的狀態(tài)標(biāo)識(shí)sign(ji,jj)更新為1，直至與所有鄰節(jié)點(diǎn)皆建立通信路徑為止，刪除sign標(biāo)記為0的鏈路項(xiàng)信息。
(3)鏈路選擇 基于區(qū)域鏈路列表ll(i)，節(jié)點(diǎn)i尋找ll(i)中由自身出發(fā)的鏈路項(xiàng)，將其sign標(biāo)記為2，刪除標(biāo)記為1的鏈路項(xiàng)信息，并廣播包含自身id和ll(i)信息的CONNECT數(shù)據(jù)包。根據(jù)所接收到的CONNECT數(shù)據(jù)，以鏈路雙向性原則確定其鄰節(jié)點(diǎn)，并將其nl列表中的相應(yīng)標(biāo)識(shí)位mark更新為1，統(tǒng)計(jì)其數(shù)目記為kmin，計(jì)算出k0與kmin的差值。按距離升序依次將個(gè)nl列表中標(biāo)識(shí)為0的節(jié)點(diǎn)標(biāo)記為2，廣播其id，保留具有雙向鏈路的鄰節(jié)點(diǎn)，將nl中相應(yīng)狀態(tài)標(biāo)識(shí)更新為 1，刪除狀態(tài)不為 1的鄰節(jié)點(diǎn)信息項(xiàng)。
(4)功率調(diào)整 最后，節(jié)點(diǎn)i確定的發(fā)射功率應(yīng)保證與其所有鄰節(jié)點(diǎn)(位于已更新的鄰居列表nl中)皆能正常通信，即節(jié)點(diǎn)i的發(fā)射半徑為di=max{d(i,j)|j∈nl(i) } 。
5 實(shí)驗(yàn)分析
本文使用仿真工具 Matlab實(shí)現(xiàn)k連通算法k-Grid(k=2)[7]、無(wú)標(biāo)度算法 EAEM(m0=2,m=1)[14]以及FTCA算法，并比較所得網(wǎng)絡(luò)拓?fù)涞墓?jié)能性和容錯(cuò)能力。實(shí)驗(yàn)中參數(shù)設(shè)置如表3所示，運(yùn)行仿真實(shí)驗(yàn)50次，以下分析數(shù)據(jù)均為50次實(shí)驗(yàn)數(shù)據(jù)均值。
基于網(wǎng)絡(luò)生命期和節(jié)點(diǎn)能量耗盡故障及隨機(jī)失效故障綜合容忍能力的雙重需求，節(jié)點(diǎn)度k的量化分析結(jié)果如圖2所示，該圖直觀地描述并驗(yàn)證了k的最優(yōu)值k0的存在性。圖3描述了FTCA算法所得目標(biāo)拓?fù)渲泄?jié)點(diǎn)平均度＜k＞與其理論最優(yōu)值k0之間的偏差情況，偏差越小意味FTCA算法的準(zhǔn)確率越高。從圖2中可以看出，當(dāng)節(jié)點(diǎn)度取值為k=-ln(f0)時(shí)其生存時(shí)間t達(dá)到最大，即最優(yōu)值k0的存在性在圖中得到了很好的體現(xiàn)。從圖3中可以看出，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目增加時(shí)，F(xiàn)TCA算法所得拓?fù)涞墓?jié)點(diǎn)平均度與理論最優(yōu)值之間的偏差在減小，且最大偏差小于0.15，也就是說，F(xiàn)TCA算法可以有效保證生成拓?fù)涞臏?zhǔn)確性。
圖 4描述了原始拓?fù)浣Y(jié)構(gòu)Gs以及k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目標(biāo)拓?fù)浣Y(jié)構(gòu)圖，該圖驗(yàn)證了FTCA算法的相關(guān)拓?fù)湫再|(zhì)，如連通性、對(duì)稱性與魯棒性。從圖4可以看出，k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法均對(duì)原始拓?fù)浣Y(jié)構(gòu)Gs進(jìn)行了簡(jiǎn)化，生成的目標(biāo)拓?fù)浣Y(jié)構(gòu)都保留了雙向鏈路。另外，由于k-Grid(k=2)算法基于概率進(jìn)行拓?fù)錁?gòu)建，依據(jù)鏈路冗余實(shí)現(xiàn)拓?fù)淙蒎e(cuò)，較 EAEM(m0=2,m=1)算法和FTCA算法所得拓?fù)涓鼮槊芗?，且拓?fù)涞倪B通性不能很好地保證；而EAEM算法是根據(jù)結(jié)構(gòu)的不均勻性實(shí)現(xiàn)容錯(cuò)，F(xiàn)TCA算法是以維持各節(jié)點(diǎn)的節(jié)點(diǎn)度在某一特定值達(dá)到容錯(cuò)，兩者所得拓?fù)浣Y(jié)構(gòu)更為稀疏，且有效確保了所得拓?fù)涞娜B通。
表3 實(shí)驗(yàn)參數(shù)設(shè)置
圖2 節(jié)點(diǎn)度最優(yōu)值k0存在性分析圖
圖3 FTCA算法準(zhǔn)確性分析圖
圖4 拓?fù)浣Y(jié)構(gòu)分析圖
圖 5描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA算法所得目標(biāo)拓?fù)涞墓?jié)點(diǎn)平均發(fā)射半徑。由于較小的發(fā)射半徑能夠降低節(jié)點(diǎn)能量消耗，減少通信干擾，增大網(wǎng)絡(luò)容量，因此節(jié)點(diǎn)的發(fā)射半徑大小一定程度上能體現(xiàn)網(wǎng)絡(luò)的節(jié)能性，是容錯(cuò)拓?fù)淇刂扑惴ㄗ非蟮牧己猛負(fù)湫再|(zhì)之一。圖 6描述了k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和FTCA算法所得目標(biāo)拓?fù)涞墓?jié)點(diǎn)平均度。由于節(jié)點(diǎn)最小度為k的k連通網(wǎng)絡(luò)在任意k-1個(gè)節(jié)點(diǎn)失效后仍能保持連通，具有k-1的容錯(cuò)能力，雖然節(jié)點(diǎn)平均度為k不能保證網(wǎng)絡(luò)是k連通，但是，節(jié)點(diǎn)的平均度在一定程度上也能反映網(wǎng)絡(luò)的容錯(cuò)能力，是容錯(cuò)拓?fù)淇刂扑惴ㄗ非蟮挠忠涣己猛負(fù)湫再|(zhì)。從圖5可以看出，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)從100至500的變化中，由于FTCA算法所得拓?fù)錈o(wú)需維持k-Grid(k=2)拓?fù)涞娜哂噫溌?，也不存?EAEM(m0=2,m=1)拓?fù)涞募?度很大)節(jié)點(diǎn)，故其節(jié)點(diǎn)平均發(fā)射半徑始終遠(yuǎn)小于k-Grid(k=2)和EAEM(m0=2,m=1)拓?fù)洌⑶译S著節(jié)點(diǎn)數(shù)的增大，節(jié)點(diǎn)平均發(fā)射半徑逐漸減小，即網(wǎng)絡(luò)具有更好的節(jié)能性。從圖6可以看出，由于FTCA算法以節(jié)點(diǎn)能量故障和隨機(jī)故障的協(xié)同優(yōu)化為設(shè)計(jì)目標(biāo)，通過各節(jié)點(diǎn)維持某一特定節(jié)點(diǎn)度實(shí)現(xiàn)容錯(cuò)，所得拓?fù)涞墓?jié)點(diǎn)平均度低于k-Grid(k=2)冗余拓?fù)?，高?EAEM(m0=2,m=1)非冗余拓?fù)?，即網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)隨機(jī)失效的容忍能力介于k-Grid(k=2)拓?fù)渑cEAEM(m0=2,m=1)拓?fù)渲g。
WSNs生命期定義為有效數(shù)據(jù)采集輪數(shù)(采集1輪數(shù)據(jù)規(guī)定為全網(wǎng)中各節(jié)點(diǎn)傳輸數(shù)據(jù)1次)是評(píng)價(jià)容錯(cuò)拓?fù)淇刂扑惴ㄐ阅艿闹匾笜?biāo)，對(duì)于特定的節(jié)點(diǎn)數(shù)(100個(gè))，分別運(yùn)行k-Grid(k=2)算法、EAEM(m0=2,m=1)算法和 FTCA 算法，然后以 Poisson規(guī)則隨機(jī)地失效節(jié)點(diǎn)，直到可用節(jié)點(diǎn)(位于最大連通分支中)數(shù)占網(wǎng)絡(luò)原有節(jié)點(diǎn)數(shù)的50%時(shí)停止，此時(shí)網(wǎng)絡(luò)生命期也終止。圖7給出了上述算法所得目標(biāo)拓?fù)湓诠?jié)點(diǎn)能量耗盡與隨機(jī)失效故障共存下的生命期變化情況。其中，圖 7(a)描述了從開始至網(wǎng)絡(luò)終止整個(gè)運(yùn)行時(shí)間段內(nèi)的節(jié)點(diǎn)隨機(jī)失效現(xiàn)象，圖7(b)為該時(shí)間段內(nèi)網(wǎng)絡(luò)可用節(jié)點(diǎn)數(shù)的變化情況，圖 7(c)為網(wǎng)絡(luò)出現(xiàn)節(jié)點(diǎn)能量耗盡故障的運(yùn)行時(shí)刻，圖7(d)為網(wǎng)絡(luò)出現(xiàn)節(jié)點(diǎn)隨機(jī)失效故障的運(yùn)行時(shí)刻。可見，k-Grid(k=2)算法所得拓?fù)鋵?duì)隨機(jī)節(jié)點(diǎn)失效有較強(qiáng)的容錯(cuò)能力，在網(wǎng)絡(luò)終止前僅出現(xiàn)一次因隨機(jī)失效節(jié)點(diǎn)引發(fā)的網(wǎng)絡(luò)分割現(xiàn)象(圖 7(d))，但因多節(jié)點(diǎn)的能量耗盡故障(圖7(c))導(dǎo)致網(wǎng)絡(luò)較早終止(圖7(b))；EAEM(m0=2,m=1)算法所得網(wǎng)絡(luò)拓?fù)涞娜蒎e(cuò)能力恰與k-Grid(k=2)拓?fù)湎喾?，在網(wǎng)絡(luò)終止前沒有出現(xiàn)過節(jié)點(diǎn)能量耗盡現(xiàn)象(圖 7(c))，卻因部分隨機(jī)失效節(jié)點(diǎn)發(fā)生網(wǎng)絡(luò)分割(圖 7(d))，最終因集散節(jié)點(diǎn)的能量耗盡故障而較早終止運(yùn)行(圖 7(b))；FTCA算法由于考慮了節(jié)點(diǎn)能量耗盡故障對(duì)網(wǎng)絡(luò)容錯(cuò)性的影響，并以優(yōu)化節(jié)點(diǎn)綜合故障為設(shè)計(jì)目標(biāo)，所得拓?fù)浣Y(jié)構(gòu)在最大化網(wǎng)絡(luò)生命期(圖 7(b))和提升網(wǎng)絡(luò)綜合故障容忍能力方面(圖 7(c)和圖 7(d))均體現(xiàn)出極佳的效果，大大延長(zhǎng)了網(wǎng)絡(luò)的生命期，增強(qiáng)了網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)能量耗盡故障和隨機(jī)失效故障的綜合容錯(cuò)性。
圖5 節(jié)點(diǎn)平均發(fā)射半徑分析圖
圖6 節(jié)點(diǎn)平均度分析圖
圖7 節(jié)點(diǎn)能量耗盡與隨機(jī)失效綜合故障下網(wǎng)絡(luò)生命期分析圖
6 結(jié)束語(yǔ)
本文提出了一種基于節(jié)點(diǎn)能量耗盡和隨機(jī)失效綜合故障模型的WSNs容錯(cuò)拓?fù)淇刂品椒‵TCA，使得生成的網(wǎng)絡(luò)拓?fù)渚哂休^大生命期和對(duì)節(jié)點(diǎn)能量耗盡及隨機(jī)失效強(qiáng)容錯(cuò)的雙重性能。另外，通過對(duì)節(jié)點(diǎn)故障模型的分析得出，當(dāng)節(jié)點(diǎn)度為 min{kmax,- ln (f0)}時(shí)可以獲得滿足節(jié)能和容錯(cuò)雙重需求的目標(biāo)拓?fù)?；并?duì)FTCA算法實(shí)驗(yàn)數(shù)據(jù)的分析得出，相對(duì)k-Grid(k=2)算法和 EAEM(m0=2,m=1)算法，F(xiàn)TCA算法由于采用了節(jié)點(diǎn)能量故障和隨機(jī)故障綜合優(yōu)化的節(jié)點(diǎn)度取值，大大延緩了因節(jié)點(diǎn)能量耗盡及隨機(jī)失效綜合故障造成的網(wǎng)絡(luò)生命期終止時(shí)刻，有效地增強(qiáng)了網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)能量耗盡及隨機(jī)失效的綜合容錯(cuò)能力。
[1]Akyildiz I F, Su W, Sankarasubramaniam Y,et al.. Wireless sensor networks: a survey[J].Computer Networks, 2002, 38(4):393-422.
[2]Chen I R, Speer A P, and Eltoweissy M. Adaptive fault-tolerant QoS control algorithm for maximizing system lifetime of query-based wireless sensor networks[J].IEEE Transactions on Dependable and Secure Computing, 2011,8(2): 161-176.
[3]Lee S and Younis M. Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J].Journal of Parallel and Distributed Computing, 2010,70(5): 525-536.
[4]Bari A, Jaekel A, Jiang J,et al.. Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirement[J].Computer Communications, 2012, 35(3):320-333.
[5]Zhang W Y, Xue G L, and Misra S. Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms[C]. Proceedings-IEEE INFOCOM, Anchorage,AK, 2007: 1649-1657.
[6]Zhang K, Han D H, and Feng H P. A model of linear expanding in the local-world based on the laws of internal evolution of the wireless sensor networks[C]. Proceedings of the 2010 International Conference on Computer Application and System Modeling, Taiyuan, China, 2010: 357-360.
[7]Dai F and Wu J. On constructing k-connected k-dominating set in wireless Ad hoc and sensor networks[J].Journal of Parallel and Distributed Computing, 2006, 66(7): 947-958.
[8]Zhao Y X, Wu J, Li F,et al.. VBS: maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones[C]. Proceedings-IEEE INFOCOM, San Diego, CA,2010: 1-5.
[9]Forghani A and Rahmani A M. Multi state fault tolerant topology control algorithm for wireless sensor networks[C].Proceedings of the 2008 2nd International Conference on Future Generation Communication and Networking, Hainan Island, China, 2008: 433-436.
[10]王良民, 馬建峰, 王超. 無(wú)線傳感器網(wǎng)絡(luò)拓?fù)涞娜蒎e(cuò)度與容侵度[J]. 電子學(xué)報(bào), 2006, 34(8): 1446-1451.
Wang L M, Ma J F, and Wang C. Degree of fault-tolerance and intrusion-tolerance for topologies of wireless sensor networks[J].Acta Electronic Sinica, 2006, 34(8): 1446-1451.
[11]Barabasi A L and Albert R. Emergence of scaling in random networks[J].Science, 1999, 286(5439): 509-512.
[12]Cohen R, Erez K, Ben A D,et al.. Resilience of the internet to random breakdowns[J].Physical Review Letters, 2000, 85(21):4626-4628.
[13]陳力軍, 劉明, 陳道蓄, 等. 基于隨機(jī)行走的無(wú)線傳感器網(wǎng)絡(luò)簇間拓?fù)溲莼痆J]. 計(jì)算機(jī)學(xué)報(bào), 2009, 32(1): 69-76.
Chen L J, Liu M, Chen D X,et al.. Topology evolution of wireless sensor networks among cluster heads by random walkers[J].Chinese Journal of Computers, 2009, 32(1): 69-76.
[14]Zhu H L, Luo H, Peng H P,et al.. Complex networks-based energy-efficient evolution model for wireless sensor networks[J].Chaos,Solitons and Fractals, 2009, 41(4):1828-1835.
[15]Qi X Q, Ma S Q, and Zheng G Z. Topology evolution of wireless sensor networks based on adaptive free-scale networks[J].Journal of Information and Computational Science, 2011, 8(3): 467-475.
[16]Mizanian K, Yousefi H, and Jahangir A H. Modeling and evaluating reliable real-time degree in multi-hop wireless sensor networks[C]. Proceedings of the 2009 IEEE Sarnoff Symposium, Princeton, NJ, 2009: 1-6.
[17]Heizelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. Proceedings of the Hawaii International Conference on System Sciences, Maui, USA,2000: 1-10.
[18]Kleinrock L and Silvester J. Optimum transmission radii for packet radio networks or why six is a magic number[C].Proceedings of the National Telecommunications Conference,Birmingham Ala, 1978: 1-5.
猜你喜歡
小學(xué)生學(xué)習(xí)指導(dǎo)(高年級(jí))(2024年4期)2024-05-07 03:28:46
玉溪師范學(xué)院學(xué)報(bào)(2023年3期)2023-08-31 14:11:56
小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2021年4期)2021-04-27 10:14:56
課堂內(nèi)外(初中版)(2020年5期)2020-06-19 08:11:11
大氣科學(xué)學(xué)報(bào)(2017年3期)2017-05-30 10:48:04
河北工業(yè)大學(xué)學(xué)報(bào)(2016年6期)2016-04-16 02:54:19
項(xiàng)目管理技術(shù)(2015年10期)2015-12-26 09:36:04
傳感器與微系統(tǒng)(2014年1期)2014-09-20 08:03:28
華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2014年3期)2014-03-11 16:18:15
技術(shù)經(jīng)濟(jì)(2014年10期)2014-02-28 01:30:01
