王瑩
摘? 要: 介紹無標(biāo)度模型的特點;通過經(jīng)典的無標(biāo)度網(wǎng)絡(luò)的構(gòu)建過程,介紹結(jié)合無線傳感器網(wǎng)絡(luò)自身特點建立的傳感網(wǎng)無標(biāo)度演化模型的研究現(xiàn)狀;分析和比較不同方法的特點。現(xiàn)有方法雖然可以延長網(wǎng)絡(luò)的生命周期,但仍然存在一些問題?;诖?,總結(jié)傳感網(wǎng)無標(biāo)度演化模型在節(jié)點度,節(jié)點剩余能量、鏈路增減和節(jié)點生命期等方面可能存在的研究熱點,提出了無線傳感器網(wǎng)絡(luò)發(fā)展的新方向。
關(guān)鍵詞: 無標(biāo)度模型; 無線傳感器網(wǎng)絡(luò); 節(jié)點度; 節(jié)點剩余能量
中圖分類號:TP393? ? ? ? ? 文獻(xiàn)標(biāo)志碼:A? ? ?文章編號:1006-8228(2019)05-09-03
Abstract: This paper introduces the characteristics of the scale-free model. Through the construction process of classic scale-free networks, the research status of the scale-free evolution model of sensor networks built by combining with the characteristics of wireless sensor networks is introduced; the characteristics of different methods are analyzed and compared. Although the existing methods can extend the networks lifetime, there are still some problems. On this basis, the research hotspots of scale-free evolution model of wireless sensor networks are summarized in node degree, node residual energy, link increase or decrease and node lifetime etc., putting forward the new development direction of wireless sensor networks.
Key words: scale-free model; wireless sensor networks; node degree; node residual energy
0 引言
無線傳感器網(wǎng)絡(luò)是由大量傳感器節(jié)點通過自組織形式,以多跳方式進(jìn)行傳輸數(shù)據(jù)的[1],可實現(xiàn)數(shù)據(jù)的采集量化、處理融合和傳輸應(yīng)用,可用于軍事偵察、環(huán)境監(jiān)測、醫(yī)療監(jiān)護(hù)、空間探索和城市交通管理[2]。布置在惡劣環(huán)境中的無線傳感器網(wǎng)絡(luò)是一個能量受限的網(wǎng)絡(luò),經(jīng)常有節(jié)點失效的情況發(fā)生[3]。
由于無線傳感器網(wǎng)絡(luò)是一個動態(tài)的網(wǎng)絡(luò),網(wǎng)絡(luò)內(nèi)的節(jié)點可能會因為能量耗盡或其他故障退出網(wǎng)絡(luò);有些節(jié)點可能處于工作狀態(tài),而有些節(jié)點可能處于關(guān)閉狀態(tài)即沒有參與網(wǎng)絡(luò)通訊;也有可能會新增大量的節(jié)點融入網(wǎng)絡(luò)。這些都會使網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)隨時發(fā)生變化。無線傳感器網(wǎng)絡(luò)通常將網(wǎng)絡(luò)中最早失效的傳感器節(jié)點的生存時間定義為網(wǎng)絡(luò)的生命期[4],網(wǎng)絡(luò)擁有較長網(wǎng)絡(luò)生命周期的容錯拓?fù)鋵τ谔岣邿o線傳感器網(wǎng)絡(luò)的性能具有重要的意義。本文針對無線傳感器網(wǎng)絡(luò)生存性問題,對目前已有的無標(biāo)度拓?fù)淠P脱娱L網(wǎng)絡(luò)生命期的方法進(jìn)行分析。
1 無標(biāo)度網(wǎng)絡(luò)概述
無標(biāo)度網(wǎng)絡(luò)是指節(jié)點度服從冪律分布的網(wǎng)絡(luò),通常把節(jié)點度服從冪律分布的特性稱為無標(biāo)度特性。無標(biāo)度網(wǎng)絡(luò)建模把重點放在把握網(wǎng)絡(luò)的動態(tài)演化的特性,用無標(biāo)度理論構(gòu)建網(wǎng)絡(luò)拓?fù)?,不僅對無線傳感器網(wǎng)絡(luò)節(jié)點隨機失效具有很強的容忍能力,還可以延長網(wǎng)絡(luò)生命期。
自Barabási和Albert于1999年首次提出無標(biāo)度網(wǎng)絡(luò)的概念以來[5],無論在實證研究上,還是在建模和理論分析方面,無標(biāo)度網(wǎng)絡(luò)的研究都取得了令人矚目的成果。實證表明許多大型網(wǎng)絡(luò)是無標(biāo)度的,即它們的度分布服從冪律分布,與傳統(tǒng)隨機網(wǎng)絡(luò)的泊松分布明顯不同。對于拓?fù)淇刂蒲娱L網(wǎng)絡(luò)生命期的研究[6-11],Barabási通過實證研究,發(fā)現(xiàn)在隨機節(jié)點失效下,無標(biāo)度拓?fù)湎鄬﹄S機網(wǎng)絡(luò)拓?fù)溆兄軓姷娜蒎e性,進(jìn)而延長網(wǎng)絡(luò)壽命。
近年來,將無標(biāo)度特性引入到無線傳感器網(wǎng)絡(luò)中成為研究的一個熱點,無標(biāo)度拓?fù)鋵?jié)點隨機失效的強容錯性在一定程度上能夠延長網(wǎng)絡(luò)的生命期。
2 傳感網(wǎng)中無標(biāo)度拓?fù)淠P头诸?/p>
2.1 BA模型
文獻(xiàn)[5]中首次提出了某些大型網(wǎng)絡(luò)能夠自組織成無標(biāo)度網(wǎng)絡(luò)的依據(jù),網(wǎng)絡(luò)通過增添節(jié)點在不斷增長和新節(jié)點總是擇優(yōu)連接到度高的節(jié)點上。BA模型第一次把冪律度分布引入到網(wǎng)絡(luò),它描述的是一個生長的開放系統(tǒng)。其拓?fù)渖蛇^程如下。
⑴ 增長:初始網(wǎng)絡(luò)由m0個節(jié)點組成,在此后的每一個時間間隔內(nèi),新增節(jié)點與原有節(jié)點發(fā)生m條邊連接,且m ⑵ 擇優(yōu)連接:新節(jié)點與節(jié)點i相連的概率π(ki)取決于節(jié)點i的度ki。 其中,為已存在節(jié)點的度總和。 2.2 B模型 文獻(xiàn)[12]是在BA模型的基礎(chǔ)上考慮了拓?fù)洚a(chǎn)生過程中鏈路增減的變化狀態(tài)。基于BA模型的增長和擇優(yōu)連接機制,通過優(yōu)化拓?fù)渖梢?guī)則來提升網(wǎng)絡(luò)性能。新節(jié)點與節(jié)點i相連的概率π(ki)取決于節(jié)點i的度ki。演化過程如下。 ⑴ 增長:同BA模型。 ⑵ 擇優(yōu)連接:同BA模型,新節(jié)點與節(jié)點i相連的概率π(ki)同⑴。 ⑶ 鏈路刪除:刪除以節(jié)點i為端點的一條邊的概率π*(ki)為: 其中,為概率歸一化系數(shù);N(t)為t時間步后形成網(wǎng)絡(luò)的規(guī)模。 2.3 EAEM模型 文獻(xiàn)[13]是在BA無標(biāo)度模型的基礎(chǔ)上,通過優(yōu)化拓?fù)渖梢?guī)則來提升網(wǎng)絡(luò)性能。其增長機制與BA模型相同,但擇優(yōu)連接機制為:當(dāng)新節(jié)點加入到網(wǎng)絡(luò)中時,與節(jié)點i相連接的概率取決于節(jié)點i的剩余能量E及節(jié)點的度。 其中,f(E)為增函數(shù);local area為節(jié)點i鄰節(jié)點區(qū)域。 2.4 FTEL模型 文獻(xiàn)[14]中劉浩然等人將節(jié)點的剩余能量和節(jié)點的負(fù)載相結(jié)合,作為節(jié)點的適應(yīng)度函數(shù),對擇優(yōu)連接概率進(jìn)行改進(jìn)。 其中,ηi為適應(yīng)度函數(shù),,Ei為節(jié)點i的剩余能量,為節(jié)點的結(jié)構(gòu)負(fù)載。local area為節(jié)點i鄰節(jié)點區(qū)域。 2.5 SIOT模型 文獻(xiàn)[15]中借助節(jié)點批量到達(dá)的Poisson網(wǎng)絡(luò)模型,在局域世界內(nèi)構(gòu)建新的無標(biāo)度拓?fù)浣Y(jié)構(gòu)。演化模型采用經(jīng)典BA無標(biāo)度網(wǎng)絡(luò)的增長和擇優(yōu)連接,在擇優(yōu)增長時,新節(jié)點n僅在其傳輸范圍內(nèi)選擇連接節(jié)點i,且此時的擇優(yōu)連接概率取決于節(jié)點當(dāng)前的剩余能量Ei和節(jié)點度ki。 其中An為新節(jié)點n的鄰節(jié)點集,β1為剩余能量調(diào)節(jié)因子,β2為節(jié)點度調(diào)節(jié)因子,且β1>0,β2>0。 服從冪律分布的無標(biāo)度網(wǎng)絡(luò),可以用網(wǎng)絡(luò)結(jié)構(gòu)熵來度量拓?fù)涞娜萸中?,網(wǎng)絡(luò)結(jié)構(gòu)熵。 2.6 BDDB模型 文獻(xiàn)[16]中劉浩然等人基于無標(biāo)度拓?fù)涞男纬蓷l件,設(shè)置優(yōu)先連接概率時綜合考慮節(jié)點度、剩余能量和節(jié)點間距離,并在拓?fù)錁?gòu)建過程中引入鏈路刪除機制。擇優(yōu)連接概率如下。 其中,F(xiàn)為適應(yīng)度函數(shù),,di表示節(jié)點間的距離;Ei為節(jié)點剩余能量,Ei=E0-μki,E0表示節(jié)點初始能量,μ為節(jié)點剩余能量與節(jié)點度的調(diào)節(jié)因子。 鏈路刪除機制: 其中,N(t)是t個時間步后形成網(wǎng)絡(luò)的規(guī)模。 2.7 EETM模型 文獻(xiàn)[17]中劉洲洲等人根據(jù)無標(biāo)度理論,依據(jù)無線傳感器網(wǎng)絡(luò)節(jié)點的能量和通信半徑的關(guān)系,提出一種能量有效的無標(biāo)度拓?fù)溲莼P?,使?jié)點可以根據(jù)自身的能量狀況選擇合適的通信半徑,并使剩余能量大的節(jié)點擁有較大的連接概率。擇優(yōu)連接概率如下: 其中:j∈An為新加入的節(jié)點h的鄰節(jié)點集;di=f(Ri)為關(guān)于節(jié)點通信半徑Ri的連續(xù)函數(shù),由節(jié)點的剩余能量和網(wǎng)絡(luò)中所有節(jié)點的平均剩余能量決定;β1、β2為調(diào)節(jié)參數(shù),可以調(diào)節(jié)節(jié)點度和節(jié)點通信半徑在擇優(yōu)連接時的權(quán)重。 2.8 APSL算法 文獻(xiàn)[18]中按照WSNs拓?fù)涫菑囊粋€小規(guī)模網(wǎng)絡(luò)逐層向外增長,在單位時間間隔內(nèi)可能同時有多個新節(jié)點加入網(wǎng)絡(luò),按照Possion分布批量添加新節(jié)點生成網(wǎng)絡(luò)。擇優(yōu)連接概率與節(jié)點度,節(jié)點間的鏈路質(zhì)量狀況RSSI(吸引度)有關(guān)。 其中,0<ε<1,i=1,2,…,m0+t-1,ki為節(jié)點i的節(jié)點度,βi為節(jié)點i的吸引度。 3 現(xiàn)有方法比較與分析 表1所示為傳感網(wǎng)中無標(biāo)度拓?fù)淠P椭懈鱾€屬性的比較。由表1可知: ⑴ 經(jīng)典無標(biāo)度網(wǎng)絡(luò)BA模型第一次把冪律度分布引入到網(wǎng)絡(luò),它描述的是一個生長的開放系統(tǒng)。BA模型的重要意義在于它把實際復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性,歸結(jié)為增長和擇優(yōu)連接這兩個非常簡單明了的機制。 ⑵ 現(xiàn)有無標(biāo)度網(wǎng)絡(luò)模型都是在BA模型的基礎(chǔ)上,結(jié)合無線傳感器網(wǎng)絡(luò)自身的特點,考慮節(jié)點剩余能量,節(jié)點負(fù)載,節(jié)點間距離等因素,設(shè)計出符合無線傳感器網(wǎng)絡(luò)特點的拓?fù)淠P?,能夠在一定程度上延長網(wǎng)絡(luò)生命期,但都有一定的局限性。 4 結(jié)束語 無線傳感器網(wǎng)絡(luò)由無數(shù)傳感器節(jié)點組成,通過無線通信方式形成的一個多跳的自組織網(wǎng)絡(luò)系統(tǒng),目的是協(xié)作地監(jiān)測、感知和采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)各種感知對象的信息。 本文從無標(biāo)度拓?fù)淠P偷谋匾猿霭l(fā),對經(jīng)典的無標(biāo)度拓?fù)淠P瓦M(jìn)行了分析探討。在無標(biāo)度網(wǎng)絡(luò)中大多數(shù)的節(jié)點只有一兩個連接,而少數(shù)集散節(jié)點卻有很大的度?;谶@些無標(biāo)度拓?fù)淠P?,?gòu)建出的無線傳感器網(wǎng)絡(luò)具有高可靠性和高健壯性,延長了網(wǎng)絡(luò)生命周期,也是無線傳感器網(wǎng)絡(luò)的新的研究方向。 參考文獻(xiàn)(References): [1] 劉強,黃小紅,冷延鵬,李龍江,毛玉明.一種面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)優(yōu)化部署策略(英文)[J].中國通信,2011.8:111-120 [2] 劉洲洲,王福豹.能量有效的無線傳感器網(wǎng)絡(luò)無標(biāo)度拓?fù)淠P蚚J].北京郵電大學(xué)學(xué)報,2015.38(1):87-91 [3] 尹文曉.基于無標(biāo)度理論的無線傳感器網(wǎng)絡(luò)容錯拓?fù)溲芯縖D].燕山大學(xué),2014. [4] Chen Y, Zhao Q. On the lifetime of wireless sensor?networks[J]. Communications Letters IEEE,2005.9(11):976-978 [5] Barálasi A L, Albert R. Emergence of scaling in random networks. Science,1999.286(5439):509-512 [6] 周漩,張鳳鳴,周衛(wèi)平,鄒偉,楊帆.利用節(jié)點效率評估復(fù)雜網(wǎng)絡(luò)功能魯棒性[J].物理學(xué)報,2012.61(19):1-7 [7] 陳力軍,劉明,陳道蓄,謝立.基于隨機行走的無線傳感器網(wǎng)絡(luò)簇間拓?fù)溲莼痆J].計算機學(xué)報,2009.32(1):69-76 [8] 劉彬,董明如,劉浩然,尹榮榮,韓麗.基于綜合故障的無線傳感器網(wǎng)絡(luò)無標(biāo)度容錯拓?fù)淠P脱芯縖J].物理學(xué)報,2014.63(17):105-112 [9] 孫雅靜.具有抗毀性的能耗均衡無線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯縖D].燕山大學(xué),2016. [10] 崔莉,鞠海玲,苗勇,李天璞,劉巍,趙澤.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計算機研究與發(fā)展,2005.1:163-174 [11] 尹榮榮,劉彬,劉浩然,李雅倩.無線傳感器網(wǎng)絡(luò)中無標(biāo)度拓?fù)涞膭討B(tài)容錯性分析[J].物理學(xué)報,2014.63(11):35-42 [12] Chen Q, Shi D. The modeling of scale-free networks [J].Physica A Statistical Mechanics & Its Applications, 2004.335(1-2):240-248 [13] 羅小娟.基于復(fù)雜網(wǎng)絡(luò)理論的無線傳感器網(wǎng)絡(luò)演化模型研究[D].華東理工大學(xué),2011. [14] 劉浩然,尹文曉,韓濤,董明如.一種優(yōu)化無線傳感器網(wǎng)絡(luò)生命周期的容錯拓?fù)溲芯縖J].物理學(xué)報,2014.63(4):84-90 [15] 劉浩然,尹文曉,董明如,劉彬.一種強容侵能力的無線傳感器網(wǎng)絡(luò)無標(biāo)度拓?fù)淠P脱芯縖J].物理學(xué)報,2014.63(9):83-90 [16] 劉浩然,孫雅靜,劉彬,韓麗,尹榮榮.能耗均衡的無線傳感器網(wǎng)絡(luò)無標(biāo)度容錯拓?fù)淠P蚚J].計算機學(xué)報,2017.40(8):1843-1855 [17] 劉洲洲,王福豹.能量有效的無線傳感器網(wǎng)絡(luò)無標(biāo)度拓?fù)淠P蚚J].北京郵電大學(xué)學(xué)報,2015.38(1):87-91 [18] 李曦達(dá),劉彬,尹榮榮,劉浩然.一種具有穩(wěn)定鏈路的冪律可調(diào)WSNs無標(biāo)度容錯拓?fù)渌惴╗J].燕山大學(xué)學(xué)報,2015.39(6):555-560