無標(biāo)度的WSNs路由算法研究

劉莉莉，徐 野

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110159)

無標(biāo)度的WSNs路由算法研究

劉莉莉，徐 野

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110159)

針對(duì)無標(biāo)度的拓?fù)涮匦?，提出一種基于無標(biāo)度的無線傳感器網(wǎng)絡(luò)路由算法。該路由算法從平均度分布和節(jié)點(diǎn)吸附性的角度出發(fā)，采用多路徑的設(shè)計(jì)原則，建立一種無標(biāo)度網(wǎng)絡(luò)模型，利用該模型建立無線傳感器網(wǎng)絡(luò)拓?fù)?，同時(shí)節(jié)點(diǎn)具有信息融合能力，提高數(shù)據(jù)的冗余可靠性，降低網(wǎng)絡(luò)吞吐量，使網(wǎng)絡(luò)能量均衡，延長(zhǎng)網(wǎng)絡(luò)生命周期。仿真結(jié)果表明，該路由算法與針對(duì)無線傳感器網(wǎng)絡(luò)的一些路由算法Flooding、LEACH和NBEERP相比，在節(jié)點(diǎn)度分布、可靠性和總體性能評(píng)價(jià)方面效果顯著。

無標(biāo)度；無線傳感器網(wǎng)絡(luò)；路由算法；網(wǎng)絡(luò)生命周期

無標(biāo)度網(wǎng)絡(luò)模型起源于1999年，當(dāng)年10月，美國(guó)的圣母大學(xué)物理系教授Barabasi和他的博士生Albert共同寫作了一篇題目為《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》[1]的論文，這篇論文在“Science”雜志上發(fā)表，它揭示了復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，即馬太定律，絕大多數(shù)節(jié)點(diǎn)的度很低，而只有少數(shù)節(jié)點(diǎn)的度很高的一種定律。經(jīng)過長(zhǎng)期的研究發(fā)現(xiàn)，無標(biāo)度網(wǎng)絡(luò)普遍存在于實(shí)際網(wǎng)絡(luò)中。Barabasi教授在此理論的基礎(chǔ)上，建立了無標(biāo)度模型，現(xiàn)在被簡(jiǎn)稱為BA模型。無標(biāo)度網(wǎng)絡(luò)的拓?fù)浞膬缏煞植?，其中，增長(zhǎng)特性和擇優(yōu)連接特性是無標(biāo)度網(wǎng)絡(luò)標(biāo)志性特征。不同的冪指數(shù)會(huì)影響網(wǎng)絡(luò)均勻性，而均勻性又對(duì)網(wǎng)絡(luò)的魯棒性產(chǎn)生一定的影響。目前的無標(biāo)度網(wǎng)絡(luò)，主要是對(duì)其拓?fù)浣Y(jié)構(gòu)特性和模型的研究，把無標(biāo)度理論應(yīng)用到無線傳感器網(wǎng)絡(luò)中的應(yīng)用還相對(duì)較少。文獻(xiàn)[2]考慮節(jié)點(diǎn)本身吸附性，在網(wǎng)絡(luò)擇優(yōu)連接上進(jìn)行改進(jìn)，分析網(wǎng)絡(luò)的度分布特性；文獻(xiàn)[3]以路徑上的節(jié)點(diǎn)強(qiáng)度乘積定義有效代價(jià)，利用信息包隊(duì)列長(zhǎng)度與發(fā)送能力之間的關(guān)系，自適應(yīng)調(diào)整鄰居節(jié)點(diǎn)權(quán)值，以提高網(wǎng)絡(luò)的吞吐量；文獻(xiàn)[4]利用無標(biāo)度網(wǎng)絡(luò)的冪律和強(qiáng)聚集特性，很好地平衡了路由表大小和伸長(zhǎng)系數(shù)的關(guān)系，提高網(wǎng)絡(luò)的擴(kuò)展性。通過設(shè)置一個(gè)閾值來約束地標(biāo)節(jié)點(diǎn)最小的覆蓋面，研究其對(duì)緊湊路由算法的影響；文獻(xiàn)[5]對(duì)網(wǎng)絡(luò)流量模型和節(jié)點(diǎn)的betweeness進(jìn)行分析和改進(jìn)，提高模型的網(wǎng)絡(luò)容量；文獻(xiàn)[6]從無標(biāo)度網(wǎng)絡(luò)的物理特性出發(fā)，綜合網(wǎng)絡(luò)節(jié)點(diǎn)隊(duì)列長(zhǎng)度，建立動(dòng)態(tài)局部路由；文獻(xiàn)[7]深入研究網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)的處理速度對(duì)路由算法設(shè)計(jì)的影響，分別從靜態(tài)和動(dòng)態(tài)的角度出發(fā)，提出參數(shù)優(yōu)化方法。文獻(xiàn)[8]基于無標(biāo)度的結(jié)構(gòu)提出了WSNs的容錯(cuò)拓?fù)淇刂扑惴?，核心思想是提高無線傳感器網(wǎng)絡(luò)的容錯(cuò)性。這些文獻(xiàn)中的路由算法從不同的角度優(yōu)化網(wǎng)絡(luò)特性，但是沒有針對(duì)網(wǎng)絡(luò)拓?fù)涮匦蕴岢龅穆酚伤惴?。無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的、廉價(jià)的、微型的傳感器組成，通過無線通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。無線傳感器網(wǎng)絡(luò)通常包括傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)，通過隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)或附近形成的自組織方式的網(wǎng)絡(luò)。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)將監(jiān)測(cè)收集的數(shù)據(jù)經(jīng)過多條路徑傳遞到匯聚節(jié)點(diǎn)，之后通過互聯(lián)網(wǎng)或衛(wèi)星送達(dá)管理節(jié)點(diǎn)。本文針對(duì)無標(biāo)度的拓?fù)涮匦裕岢鲆环N基于無標(biāo)度特性的無線傳感器網(wǎng)絡(luò)路由SFRA算法，該算法在數(shù)據(jù)傳輸、網(wǎng)絡(luò)能耗、存活節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)生命周期方面進(jìn)行相應(yīng)的仿真研究。

1 基于無標(biāo)度的網(wǎng)絡(luò)模型

無標(biāo)度網(wǎng)絡(luò)拓?fù)溆袃蓚€(gè)必不可少的形成機(jī)制：增長(zhǎng)特性和擇優(yōu)連接特性。正是因?yàn)檫@兩個(gè)特性才能對(duì)無標(biāo)度網(wǎng)絡(luò)具有冪律分布進(jìn)行解釋。所以，具有冪律分布的網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò)。根據(jù)無標(biāo)度的性質(zhì)，在無線傳感器網(wǎng)絡(luò)中建立一定的擇優(yōu)連接機(jī)制，使得傳感器節(jié)點(diǎn)的能量分布均衡，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期；也可以改變網(wǎng)絡(luò)的增長(zhǎng)機(jī)制，通過控制網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，調(diào)節(jié)網(wǎng)絡(luò)的均勻性，從而在面對(duì)隨機(jī)攻擊和特定攻擊時(shí)，提高網(wǎng)絡(luò)的魯棒性。因?yàn)槎鄶?shù)節(jié)點(diǎn)的度很少，少數(shù)節(jié)點(diǎn)的度很高，所以對(duì)那些度很高的節(jié)點(diǎn)的能耗研究就顯得尤為重要。

無標(biāo)度網(wǎng)絡(luò)不是規(guī)則網(wǎng)絡(luò)，也不是小世界網(wǎng)絡(luò)，而是一種根據(jù)一定的策略所形成的介于規(guī)則和隨機(jī)網(wǎng)絡(luò)之間的復(fù)雜網(wǎng)絡(luò)。

1.1 無標(biāo)度網(wǎng)絡(luò)屬性

無標(biāo)度網(wǎng)絡(luò)的一些基本定義如下：

定義1 設(shè)無向圖G=(V，E)，N=|V|表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目，M=|E|表示網(wǎng)絡(luò)的邊數(shù)。則節(jié)點(diǎn)i的度定義為：節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)相連接的數(shù)量，記做ki。

定義2 網(wǎng)絡(luò)中隨機(jī)一節(jié)點(diǎn)的節(jié)點(diǎn)度稱為度分布，無標(biāo)度網(wǎng)絡(luò)節(jié)點(diǎn)度服從冪律分布，度分布函數(shù)用p(k)表示，即網(wǎng)絡(luò)中任意節(jié)點(diǎn)正好有k條邊的概率。那么度為k的節(jié)點(diǎn)數(shù)目與k之間的關(guān)系為

p(k)∝k-r

(1)符合這個(gè)關(guān)系式的網(wǎng)絡(luò)就是具有冪律特性的拓?fù)洹?/p>

定義3 無標(biāo)度網(wǎng)絡(luò)的標(biāo)志性特征是增長(zhǎng)和擇優(yōu)，這也是無標(biāo)度網(wǎng)絡(luò)的形成機(jī)制。

定義4 網(wǎng)絡(luò)G中節(jié)點(diǎn)服從冪律分布，但是其缺少一個(gè)描述問題的特征尺度，所以被稱為無尺度網(wǎng)絡(luò)，也稱為無標(biāo)度網(wǎng)絡(luò)。

定義5 網(wǎng)絡(luò)節(jié)點(diǎn)的冪律分布遵從馬太定律，即絕大多數(shù)節(jié)點(diǎn)的度很低，而只有少數(shù)節(jié)點(diǎn)的度很高，將這些度很高的少數(shù)節(jié)點(diǎn)定義為熱節(jié)點(diǎn)，多數(shù)度很低的節(jié)點(diǎn)成為普通節(jié)點(diǎn)。

定義6 設(shè)節(jié)點(diǎn)自身具有吸附性，那么新加入網(wǎng)絡(luò)的節(jié)點(diǎn)與網(wǎng)絡(luò)中原來的節(jié)點(diǎn)相連接的概率取決于網(wǎng)絡(luò)中節(jié)點(diǎn)的度和節(jié)點(diǎn)自身的吸附性，稱之為偏好依附。

定義7 聚集系數(shù)：描述的是網(wǎng)絡(luò)中一節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的關(guān)系，即該節(jié)點(diǎn)在網(wǎng)絡(luò)中的聚集程度，數(shù)學(xué)表達(dá)式為

(2)

定義8 定義網(wǎng)絡(luò)中一個(gè)熱節(jié)點(diǎn)與鄰居節(jié)點(diǎn)組成的一個(gè)小規(guī)模網(wǎng)絡(luò)為整個(gè)網(wǎng)絡(luò)中的一個(gè)簇，這個(gè)熱節(jié)點(diǎn)是這個(gè)簇的簇頭CH[10]。與這些簇頭都相連的節(jié)點(diǎn)稱為匯聚節(jié)點(diǎn)。

定義9 魯棒性：無標(biāo)度網(wǎng)絡(luò)在面對(duì)隨機(jī)攻擊時(shí)，具有很高的魯棒性；在面對(duì)蓄意攻擊時(shí)具有脆弱性。

1.2 網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

基于無標(biāo)度的無線傳感器網(wǎng)絡(luò)由普通節(jié)點(diǎn)、熱節(jié)點(diǎn)、匯聚節(jié)點(diǎn)通過邊連接而成，它們之間通過邊這個(gè)鏈接進(jìn)行相互通信。熱節(jié)點(diǎn)與普通節(jié)點(diǎn)形成一個(gè)個(gè)簇群，與普通節(jié)點(diǎn)相連的熱節(jié)點(diǎn)又與上一層的熱節(jié)點(diǎn)相連接，形成上一級(jí)的簇群。匯聚節(jié)點(diǎn)與最上層的熱節(jié)點(diǎn)也形成一個(gè)簇群，這樣，整個(gè)網(wǎng)絡(luò)根據(jù)簇的等級(jí)分成好多層。

普通節(jié)點(diǎn)的作用是存儲(chǔ)和收發(fā)信息，熱節(jié)點(diǎn)的作用是接受來自普通節(jié)點(diǎn)的信息資源，將數(shù)據(jù)進(jìn)行融合后轉(zhuǎn)發(fā)給上一層熱節(jié)點(diǎn)或匯聚節(jié)點(diǎn)，所以熱節(jié)點(diǎn)需要更多穩(wěn)定的能源，而且，位置相對(duì)固定。

在初始狀態(tài)，網(wǎng)絡(luò)中包含m0個(gè)孤立的節(jié)點(diǎn)[11]。

(1)增長(zhǎng)特性：每一個(gè)時(shí)間段，有一個(gè)新的節(jié)點(diǎn)將會(huì)加入到網(wǎng)絡(luò)中，并與網(wǎng)絡(luò)中m個(gè)其他節(jié)點(diǎn)建立連接。

(2)擇優(yōu)特性：設(shè)節(jié)點(diǎn)自身吸附性為A，那么新增加的節(jié)點(diǎn)與網(wǎng)絡(luò)中某節(jié)點(diǎn)i連接上的概率Πi，被假設(shè)為正比于節(jié)點(diǎn)i的度值與本身吸附性之和：

(3)

經(jīng)過t個(gè)時(shí)間段后，得到N=t+m0個(gè)節(jié)點(diǎn)、mt條邊的網(wǎng)絡(luò)。

如圖1所示，普通節(jié)點(diǎn)與最底層的熱節(jié)點(diǎn)相連，最底層熱節(jié)點(diǎn)與上一層熱節(jié)點(diǎn)相連，最終到達(dá)匯聚節(jié)點(diǎn)。普通節(jié)點(diǎn)根據(jù)熱節(jié)點(diǎn)的度和吸附性決定加入哪個(gè)簇，并通知該熱節(jié)點(diǎn)。當(dāng)熱節(jié)點(diǎn)接收到所有加入信息后，會(huì)產(chǎn)生一個(gè)TDMA信號(hào)，并通知所有普通節(jié)點(diǎn)，普通節(jié)點(diǎn)將自己簇的簇頭信息存儲(chǔ)起來，這樣，簇頭和普通節(jié)點(diǎn)之間的通信就建立起來了。

圖1 基于無標(biāo)度特性的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

2 數(shù)值分析

對(duì)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)度分布進(jìn)行求解，這里采用連續(xù)域理論[11]的分析方法。假設(shè)一個(gè)新節(jié)點(diǎn)I在t時(shí)刻加入網(wǎng)絡(luò)，此時(shí)網(wǎng)絡(luò)中有t+m0個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)中節(jié)點(diǎn)i的度ki是連續(xù)變量，那么，ki的連續(xù)變化率可得

(4)

t時(shí)刻，網(wǎng)絡(luò)總的節(jié)點(diǎn)度為

(5)

將式(5)代入式(4)中，化簡(jiǎn)得

(6)

求解微分方程，并代入初始條件ki(ti)=m，計(jì)算化簡(jiǎn)得

(7)

(8)

(9)

該網(wǎng)絡(luò)模型的節(jié)點(diǎn)度分布可由式(9)化簡(jiǎn)得

從表11中可以看出，西部礦業(yè)股份有限公司2013～2017年的資產(chǎn)負(fù)債率分別為57%、53%、56%、59%、60%，這五年間企業(yè)的資產(chǎn)負(fù)債率波動(dòng)較小，近四年其資產(chǎn)負(fù)債率一直處于增長(zhǎng)狀態(tài)，表明企業(yè)在2014～2017年四年間長(zhǎng)期償債能力在逐年下降，但下降幅度不大，長(zhǎng)期償債能力較強(qiáng)。

(10)

由上面推導(dǎo)可見，該無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)度分布服從2(m+A)2(k+A)-3的冪律分布，可以證明該無線傳感器網(wǎng)絡(luò)具有無標(biāo)度特性。

以上主要是證明無線傳感器網(wǎng)絡(luò)模型的度分布服從冪律分布與節(jié)點(diǎn)度負(fù)冪次方相關(guān)。無標(biāo)度特性的提出，為研究無線傳感器網(wǎng)絡(luò)路由算法提供了新的思路和理論依據(jù)。

3 路由算法設(shè)計(jì)

3.1 SFRA路由

基于無標(biāo)度的無線傳感器網(wǎng)絡(luò)路由(SFRA)算法的流程如圖2所示。

圖2 SFRA算法流程

算法的具體實(shí)現(xiàn)描述如下：

(1)假設(shè)現(xiàn)在節(jié)點(diǎn)C要向節(jié)點(diǎn)B轉(zhuǎn)發(fā)數(shù)據(jù)，首先，先判斷目標(biāo)地址是否與之前的有相同的，如果有相同的，轉(zhuǎn)向(2)，否則轉(zhuǎn)向(3)；

(2)如果發(fā)送的數(shù)據(jù)內(nèi)容也是相同的，那么系統(tǒng)將自動(dòng)取消此次轉(zhuǎn)發(fā)，如果發(fā)送內(nèi)容不同，在目標(biāo)地址相同的情況下，在路由表中搜索到路徑，按照之前的發(fā)送路徑轉(zhuǎn)發(fā)數(shù)據(jù)；

(4)因?yàn)閄=Y，所以數(shù)據(jù)是在簇內(nèi)通信。確定目標(biāo)地址，獲取目標(biāo)節(jié)點(diǎn)ID號(hào)，根據(jù)最短路徑轉(zhuǎn)發(fā)數(shù)據(jù)；

(5)判斷是否存在最短路徑，若存在，則按照最短路徑轉(zhuǎn)發(fā)數(shù)據(jù)，否則轉(zhuǎn)向(6)；

(6)節(jié)點(diǎn)X把數(shù)據(jù)傳送到節(jié)點(diǎn)B所在簇的簇首Y，本算法是把該無線傳感器網(wǎng)絡(luò)看成無向圖，簇首X執(zhí)行CDZ算法[12],計(jì)算出此次轉(zhuǎn)發(fā)數(shù)據(jù)的最短路徑，然后將計(jì)算出最短路徑的路由表存儲(chǔ)到簇首的緩存中，并且另外通知此最短路徑中的節(jié)點(diǎn)[13]。

CDZ算法：將中心節(jié)點(diǎn)的一條實(shí)際存在的路徑近似跨區(qū)域節(jié)點(diǎn)之間的最短路徑。用Ci表示中心節(jié)點(diǎn)的集合(i表示節(jié)點(diǎn)個(gè)數(shù)),LCAsp：s和p的最近公共祖先。

①任意兩個(gè)屬于不同簇的節(jié)點(diǎn)s和p之間的距離：近似為這兩個(gè)節(jié)點(diǎn)到各自簇中心節(jié)點(diǎn)的距離與這兩個(gè)簇中心節(jié)點(diǎn)的距離之和：d(s,p)=d(s,Cs)+d(p,Cp)+d(Cs,Cp);

②屬于同一簇的節(jié)點(diǎn)s和p之間的距離：d(s,p)=d(s,LCAsp)+d(p,LCAsp)

(7)要發(fā)送的數(shù)據(jù)包按照路由表的最短路徑將數(shù)據(jù)從節(jié)點(diǎn)X發(fā)送到節(jié)點(diǎn)Y，然后簇首Y根據(jù)簇內(nèi)最短路徑將數(shù)據(jù)包轉(zhuǎn)發(fā)給節(jié)點(diǎn)B，完成此次轉(zhuǎn)發(fā)。轉(zhuǎn)向(1)。

3.2 路由魯棒性分析

魯棒性是指網(wǎng)絡(luò)中節(jié)點(diǎn)因?yàn)槟芰亢谋M或受到攻擊無用時(shí)，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)仍然能夠保持正常通信，網(wǎng)絡(luò)的結(jié)構(gòu)和性能仍然能夠維持基本穩(wěn)定的性質(zhì)。而路由魯棒性[14]則是代表該路由算法在遇到一些自身或外在不可控因素時(shí)的適應(yīng)能力。它是在節(jié)點(diǎn)能量、通信能力和網(wǎng)絡(luò)拓?fù)涞纫蛩刈饔孟碌暮暧^效應(yīng)。所以，路由魯棒性是評(píng)價(jià)路由算法優(yōu)劣的重要依據(jù)。

SFRA路由依賴于無標(biāo)度的拓?fù)浣Y(jié)構(gòu)，這是因?yàn)樵摕o線傳感器網(wǎng)絡(luò)模型具有無標(biāo)度特性。前面已經(jīng)介紹，無標(biāo)度網(wǎng)絡(luò)節(jié)點(diǎn)度分布服從冪律特性，所以該WSN面對(duì)隨機(jī)攻擊具有很強(qiáng)的魯棒性[15]，但熱節(jié)點(diǎn)面對(duì)蓄意攻擊時(shí)又具有相對(duì)的脆弱性，所以熱節(jié)點(diǎn)的失效必定會(huì)影響無線傳感器網(wǎng)絡(luò)的通信質(zhì)量。

(1)普通節(jié)點(diǎn)的魯棒性

當(dāng)普通節(jié)點(diǎn)因能量耗盡或受到攻擊失效時(shí)，該節(jié)點(diǎn)在失效前會(huì)發(fā)送消息通知該節(jié)點(diǎn)所在簇的熱節(jié)點(diǎn)，那么熱節(jié)點(diǎn)接收到消息后會(huì)根據(jù)簇中的情況更新路由表?？梢钥闯觯@種情況下對(duì)網(wǎng)絡(luò)中數(shù)據(jù)的通信的可靠性影響很小。

(2)熱節(jié)點(diǎn)的魯棒性

熱節(jié)點(diǎn)因?yàn)榫哂邢喈?dāng)大的度，通信消耗的能量也大得多，所以一般電源和位置相對(duì)較固定，這也是設(shè)置網(wǎng)絡(luò)拓?fù)涞幕厩疤?，一般熱?jié)點(diǎn)不會(huì)失效。但當(dāng)熱節(jié)點(diǎn)能量低于設(shè)定的閾值或受到蓄意攻擊時(shí)，該熱節(jié)點(diǎn)所在的整個(gè)簇的通信將會(huì)受到影響。一般在一定的時(shí)間間隔內(nèi)，該簇的路由不通，那么認(rèn)為該簇首失效，簇首失效之前會(huì)發(fā)送報(bào)文通知上一級(jí)的簇首節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)中近半數(shù)簇首節(jié)點(diǎn)失效時(shí)，會(huì)通知sink節(jié)點(diǎn)，sink節(jié)點(diǎn)就會(huì)廣播通知所有熱節(jié)點(diǎn)，然后熱節(jié)點(diǎn)再?gòu)V播通知普通節(jié)點(diǎn)，執(zhí)行SFRA路由算法，重新建立傳輸路由。

4 實(shí)驗(yàn)仿真分析

4.1 仿真環(huán)境

監(jiān)測(cè)區(qū)域大小為200m×200m的正方形范圍，共有無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)2000個(gè)，基站坐標(biāo)為(0,0)，傳感器節(jié)點(diǎn)的位置固定且已知，節(jié)點(diǎn)感知范圍在30m。仿真實(shí)驗(yàn)的環(huán)境：CPU為Intel Core i3；內(nèi)存2G；操作系統(tǒng)為Windows 7；仿真軟件為Matlab。軟件操作界面如圖3所示。

圖3 Matlab軟件操作界面

4.2 算法性能指標(biāo)

為了評(píng)價(jià)SFRA路由算法的性能，對(duì)無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和度分布特性、SFRA的數(shù)據(jù)傳輸、網(wǎng)絡(luò)能耗和網(wǎng)絡(luò)生命周期方面進(jìn)行仿真驗(yàn)證。網(wǎng)絡(luò)數(shù)據(jù)傳輸，即傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)進(jìn)行數(shù)據(jù)包傳送，網(wǎng)絡(luò)節(jié)點(diǎn)通過最短路徑算法進(jìn)行傳輸數(shù)據(jù)，降低了節(jié)點(diǎn)的能耗和丟包率，所以，傳輸路徑越短，跳數(shù)越少，時(shí)間就越短。該參數(shù)反映網(wǎng)絡(luò)的傳輸能力，傳輸數(shù)據(jù)包越多，說明傳輸能力越強(qiáng)。網(wǎng)絡(luò)能耗，即整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗情況。熱節(jié)點(diǎn)的能源供給較為固定，而普通節(jié)點(diǎn)的能源相對(duì)較小，所以，數(shù)量眾多的普通節(jié)點(diǎn)的能量消耗越小，網(wǎng)絡(luò)生存時(shí)間越長(zhǎng)，節(jié)能效果越好。網(wǎng)絡(luò)生命周期就是網(wǎng)絡(luò)的生存時(shí)間，即網(wǎng)絡(luò)仍然存在最大連通子圖，網(wǎng)絡(luò)能夠正常通信的時(shí)間越長(zhǎng)，網(wǎng)絡(luò)生存時(shí)間就越長(zhǎng)。在仿真環(huán)境下，將本文提出的SFRA算法和LEACH算法在前面提到的幾種性能方面進(jìn)行比較。

4.3 仿真結(jié)果與分析

圖4為無線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖，該圖的相關(guān)參數(shù)如下：初始網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)為n0=5，每次引入新節(jié)點(diǎn)時(shí)新生成的邊數(shù)m=5，網(wǎng)絡(luò)規(guī)模N=130。實(shí)驗(yàn)后該網(wǎng)絡(luò)圖的聚類系數(shù)為0.15，平均路徑長(zhǎng)度為2.35。

圖4 無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

圖5為無線傳感器網(wǎng)絡(luò)的度分布情況。分別在網(wǎng)絡(luò)規(guī)模為N=1500和N=2000的情況進(jìn)行實(shí)驗(yàn)，由圖5可以看出，傳感器節(jié)點(diǎn)在雙對(duì)數(shù)坐標(biāo)下誤差允許范圍內(nèi)服從冪律分布，與上一節(jié)進(jìn)行的理論推導(dǎo)結(jié)果相一致，驗(yàn)證了其正確性。

圖6為L(zhǎng)EACH算法和SFRA算法的數(shù)據(jù)傳輸對(duì)比。由圖6可以看出，SFRA算法的數(shù)據(jù)傳輸量比LEACH算法略低，這種情況促使網(wǎng)絡(luò)節(jié)省能量。由于算法進(jìn)行數(shù)據(jù)通信，必須通過簇首轉(zhuǎn)發(fā)數(shù)據(jù)，而簇首的存儲(chǔ)空間有限，所以單位時(shí)間內(nèi)轉(zhuǎn)發(fā)的數(shù)據(jù)也是有限的。SFRA算法有簇內(nèi)和簇間通信，且運(yùn)用最短路徑算法，將最短路徑存儲(chǔ)到路由表中，使節(jié)點(diǎn)擁有記憶功能，在此通過此路徑傳輸數(shù)據(jù)時(shí)會(huì)更快，所以傳輸數(shù)據(jù)量的速度也比LEACH算法快得多。

圖5 無線傳感器網(wǎng)絡(luò)度分布圖

圖6 LEACH和SFRA的數(shù)據(jù)傳輸對(duì)比圖

圖7反映了全網(wǎng)在初始能耗為零的情況下，兩種算法能量消耗情況。由圖7可以看出網(wǎng)絡(luò)節(jié)點(diǎn)能耗的趨勢(shì)，在300時(shí)間段內(nèi)，LEACH算法的節(jié)點(diǎn)能量幾乎耗盡，而SFRA算法的節(jié)點(diǎn)能耗相對(duì)比較緩慢從而延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。起初兩種算法的節(jié)點(diǎn)能耗差距不大，但隨著時(shí)間的增加，SFRA的能耗小于LEACH?？梢钥闯觯琒FRA相比于LEACH具有明顯能耗優(yōu)勢(shì)。由于LEACH算法定期或節(jié)點(diǎn)受到攻擊后重新競(jìng)選簇首，沒有考慮簇首節(jié)點(diǎn)剩余能量的情況，所以當(dāng)簇首選舉更換較頻繁時(shí)，隨著時(shí)間的推移，會(huì)出現(xiàn)簇首能量耗盡快，更換簇首的周期變短的情況。而SFRA根據(jù)節(jié)點(diǎn)的度和自身的吸附性選擇簇首，能夠保證網(wǎng)絡(luò)簇首節(jié)點(diǎn)死亡速度慢，增加了網(wǎng)絡(luò)的可靠性，從而延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期。

圖7 LEACH和SFRA的網(wǎng)絡(luò)能耗對(duì)比圖

圖8 LEACH和SFRA的存活節(jié)點(diǎn)數(shù)隨時(shí)間的變化對(duì)比圖

圖8反映了在兩種算法下網(wǎng)絡(luò)中節(jié)點(diǎn)存活數(shù)量隨時(shí)間的變化關(guān)系。從圖8可以看出，SFRA存活節(jié)點(diǎn)數(shù)量在任何一個(gè)單位時(shí)間內(nèi)大于LEACH，且LEACH的網(wǎng)絡(luò)生命周期只有400個(gè)時(shí)間點(diǎn)，而SFRA的網(wǎng)絡(luò)生命周期長(zhǎng)達(dá)1000個(gè)時(shí)間點(diǎn)。因?yàn)長(zhǎng)EACH在選舉簇首時(shí)并沒有考慮形成的簇首分布情況，當(dāng)選舉的簇首相對(duì)較集中時(shí)，該區(qū)域節(jié)點(diǎn)能量會(huì)消耗得很快，節(jié)點(diǎn)存活率就會(huì)降低，所以會(huì)出現(xiàn)節(jié)點(diǎn)急劇下降的情況。SFRA采用多跳的形式進(jìn)行通信，網(wǎng)絡(luò)吞吐量不大，所以節(jié)點(diǎn)存活時(shí)間較長(zhǎng)，具有明顯優(yōu)勢(shì)。

4.4 仿真評(píng)價(jià)

主要將SFRA算法與Flooding算法、LEACH算法和NEBBRP算法進(jìn)行比較分析。

4.4.1 總體性能評(píng)價(jià)

Flooding算法是平面式路由，采用廣播的方式進(jìn)行選擇路徑，所以計(jì)算復(fù)雜度較低。LEACH算法、SFRA算法和NEBBRP算法是層次型路由，計(jì)算復(fù)雜度較高。但SFRA算法僅增加了吸附性這個(gè)因素，所以實(shí)現(xiàn)起來跟LEACH算法相似。表1為四種路由算法的總體性能評(píng)價(jià)。

表1 四種路由算法的總體性能評(píng)價(jià)

4.4.2 路由可靠性評(píng)價(jià)

對(duì)四種路由算法進(jìn)行仿真，測(cè)試對(duì)數(shù)據(jù)感知的可靠性。對(duì)四種模型中sink節(jié)點(diǎn)所接收到的數(shù)據(jù)報(bào)文進(jìn)行統(tǒng)計(jì)，從而判斷可靠性能。SFRA算法采用信息融合技術(shù)，所以報(bào)文流量最低，所以可靠性最高。表2為四種路由算法的可靠性評(píng)價(jià)。

表2 四種路由算法的可靠性評(píng)價(jià) %

4.4.3 網(wǎng)絡(luò)節(jié)點(diǎn)度分布的評(píng)價(jià)

無標(biāo)度網(wǎng)絡(luò)節(jié)點(diǎn)度分布為冪律分布，冪指數(shù)為大于2的任意有理數(shù)，且是可調(diào)節(jié)的。無標(biāo)度網(wǎng)絡(luò)的通信效率最高。Flooding算法所形成網(wǎng)絡(luò)的節(jié)點(diǎn)度分布是均勻分布，是規(guī)則網(wǎng)絡(luò)，平均連接度是6。LEACH算法沒有規(guī)定的度分布，且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也是相對(duì)隨機(jī)，平均連接度為4。表3為四種路由算法的網(wǎng)絡(luò)節(jié)點(diǎn)度分布。

表3 四種路由算法的網(wǎng)絡(luò)節(jié)點(diǎn)度分布

從以上幾組仿真分析來看，SFRA算法在總體評(píng)價(jià)、路由可靠性和節(jié)點(diǎn)度分布三個(gè)方面均有優(yōu)勢(shì)。滿足能量有限、動(dòng)態(tài)拓?fù)湫詿o線傳感器網(wǎng)絡(luò)路由的需求，并能夠使傳感節(jié)點(diǎn)更加長(zhǎng)期有效地工作。

5 結(jié)束語(yǔ)

研究了一種基于無標(biāo)度拓?fù)涮匦缘臒o線傳感器網(wǎng)絡(luò)路由算法。將無標(biāo)度理論應(yīng)用到無線傳感器網(wǎng)絡(luò)的路由算法研究中，并針對(duì)無標(biāo)度特殊的拓?fù)浣Y(jié)構(gòu)，采用CDZ算法計(jì)算數(shù)據(jù)傳輸最短路徑。大量仿真實(shí)驗(yàn)表明，該算法在降低傳感器網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期等方面比傳統(tǒng)無線傳感器網(wǎng)絡(luò)路由算法有較大優(yōu)勢(shì)，可應(yīng)用于無線傳感器網(wǎng)絡(luò)中，并對(duì)無線傳感器網(wǎng)絡(luò)路由算法研究提供了理論依據(jù)，為以后的研究奠定了基礎(chǔ)。

[1]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[2]申超杰.改進(jìn)的BA復(fù)雜網(wǎng)絡(luò)模型度分布的演化[D].天津：河北工業(yè)大學(xué),2007.

[3]郭文忠,劉漳輝,王小溪,等.含權(quán)無標(biāo)度網(wǎng)絡(luò)中帶自適應(yīng)系數(shù)的混合路由算法[J].小型微型計(jì)算機(jī)系統(tǒng),2014(3):448-452.

[4]田勇,唐禎安,喻言.能量均衡的室內(nèi)無線傳感器網(wǎng)絡(luò)自適應(yīng)分簇路由算法[J].電子與信息學(xué)報(bào),2013,35(12):2992-2998.

[5]李智楠,朱磊,陳劍斌.一種改進(jìn)的無標(biāo)度網(wǎng)絡(luò)模型[J].軍事通信技術(shù),2010(2):35-39.

[6]文宏,樊曉平,張會(huì)福,等.無標(biāo)度網(wǎng)絡(luò)上的動(dòng)態(tài)局部路由策略設(shè)計(jì)[J].Computer Engineering and Applications,2014,50(20):10-14.

[7]文宏,樊曉平,張會(huì)福,等.無標(biāo)度網(wǎng)絡(luò)局部路由算法優(yōu)化與設(shè)計(jì)[J].湖南大學(xué)學(xué)報(bào):自然科學(xué)版,2014,41(10):122-128.

[8]韓濤.基于無標(biāo)度理論的 WSNs 拓?fù)淇刂扑惴ㄑ芯縖D].秦皇島：燕山大學(xué),2014.

[9]汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社有限公司,2006.

[10]Xu J,Wang X F.Cascading failures in scale-free coupled map lattices[J].Physica A:Statistical Mechanics and its Applications,2005,349(3):685-692.

[11]蘇威積,趙海,張文波,等.基于嵌入式技術(shù)的傳感器網(wǎng)絡(luò)無尺度路由算法[J].計(jì)算機(jī)工程,2006,32(14):87-88.

[12]唐晉韜,王挺,王戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報(bào),2011,22(10):2279-2290.

[13]Tang F,You I,Guo S,et al.A chain-cluster based routing algorithm for wireless sensor networks[J].Journal of intelligent manufacturing,2012,23(4):1305-1313.

[14]Ye F,Zhong G,Lu S,et al.A robust data delivery protocol for large scale sensor networks[C]//Information Processing in Sensor Networks.Springer Berlin Heidelberg,2003:658-673.

[15]Kollios G,Byers J W,Considine J,et al.Robust Aggregation in Sensor Networks[J].IEEE Data Eng.Bull.,2005,28(1):26-32.

(責(zé)任編輯：馬金發(fā))

Research on the Scale-free WSNs Routing Algorithm

LIU Lili,XU Ye

(Shenyang Ligong University,Shenyang 110159,China)

Based on the topological characteristics of scale-free,a kind of wireless sensor network routing algorithm is put forward.From the perspective of the average degree distribution and the adsorption of nodes in this routing algorithm,multipath designing principle is adopted,which builds a scale-free network model.And wireless sensor network topology is established based on the model,nodes with information fusion ability at the same time,which improves data reliability redundancy and reduces network throughput.So network energy becomes balanced,which prolongs network life cycle.Simulation results show that the routing algorithm has more significant effect on the node degree distribution,reliability and overall performance evaluation in comparison with some other routing algorithms such as Flooding,LEACH and NBEERP.

scale-free;wireless sensor network;routing algorithm;network life cycle

2016-03-24

國(guó)家自然科學(xué)基金面上資助項(xiàng)目(61373159)；遼寧省高等學(xué)校優(yōu)秀人才支持計(jì)劃資助項(xiàng)目(LJQ2015095)；沈陽(yáng)市科技應(yīng)用基

礎(chǔ)研究計(jì)劃資助項(xiàng)目(F13-316-1-22)；沈陽(yáng)理工大學(xué)重點(diǎn)學(xué)科、重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目(4771004kfs18)

劉莉莉(1992—)，女，碩士研究生；通訊作者：徐野(1976—)，男，教授，博士，研究方向：復(fù)雜互聯(lián)系統(tǒng)與大規(guī)模網(wǎng)絡(luò)。

1003-1251(2016)06-0059-07

TP393

A