劉莉莉，徐 野

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

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

劉莉莉，徐 野

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

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

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

無標(biāo)度網(wǎng)絡(luò)模型起源于1999年，當(dāng)年10月，美國的圣母大學(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)過長期的研究發(fā)現(xiàn)，無標(biāo)度網(wǎng)絡(luò)普遍存在于實(shí)際網(wǎng)絡(luò)中。Barabasi教授在此理論的基礎(chǔ)上，建立了無標(biāo)度模型，現(xiàn)在被簡稱為BA模型。無標(biāo)度網(wǎng)絡(luò)的拓?fù)浞膬缏煞植?，其中，增長特性和擇優(yōu)連接特性是無標(biāo)度網(wǎng)絡(luò)標(biāo)志性特征。不同的冪指數(shù)會影響網(wǎng)絡(luò)均勻性，而均勻性又對網(wǎng)絡(luò)的魯棒性產(chǎn)生一定的影響。目前的無標(biāo)度網(wǎng)絡(luò)，主要是對其拓?fù)浣Y(jié)構(gòu)特性和模型的研究，把無標(biāo)度理論應(yīng)用到無線傳感器網(wǎng)絡(luò)中的應(yīng)用還相對較少。文獻(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)度乘積定義有效代價，利用信息包隊列長度與發(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)聚集特性，很好地平衡了路由表大小和伸長系數(shù)的關(guān)系，提高網(wǎng)絡(luò)的擴(kuò)展性。通過設(shè)置一個閾值來約束地標(biāo)節(jié)點(diǎn)最小的覆蓋面，研究其對緊湊路由算法的影響；文獻(xiàn)[5]對網(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)隊列長度，建立動態(tài)局部路由；文獻(xiàn)[7]深入研究網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)的處理速度對路由算法設(shè)計的影響，分別從靜態(tài)和動態(tài)的角度出發(fā)，提出參數(shù)優(yōu)化方法。文獻(xiàn)[8]基于無標(biāo)度的結(jié)構(gòu)提出了WSNs的容錯拓?fù)淇刂扑惴?，核心思想是提高無線傳感器網(wǎng)絡(luò)的容錯性。這些文獻(xiàn)中的路由算法從不同的角度優(yōu)化網(wǎng)絡(luò)特性，但是沒有針對網(wǎng)絡(luò)拓?fù)涮匦蕴岢龅穆酚伤惴?。無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由部署在監(jiān)測區(qū)域內(nèi)大量的、廉價的、微型的傳感器組成，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)。無線傳感器網(wǎng)絡(luò)通常包括傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)和管理節(jié)點(diǎn)，通過隨機(jī)部署在監(jiān)測區(qū)域內(nèi)或附近形成的自組織方式的網(wǎng)絡(luò)。在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)將監(jiān)測收集的數(shù)據(jù)經(jīng)過多條路徑傳遞到匯聚節(jié)點(diǎn)，之后通過互聯(lián)網(wǎng)或衛(wèi)星送達(dá)管理節(jié)點(diǎn)。本文針對無標(biāo)度的拓?fù)涮匦?，提出一種基于無標(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ù)溆袃蓚€必不可少的形成機(jī)制：增長特性和擇優(yōu)連接特性。正是因?yàn)檫@兩個特性才能對無標(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)的能量分布均衡，從而延長網(wǎng)絡(luò)的生命周期；也可以改變網(wǎng)絡(luò)的增長機(jī)制，通過控制網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，調(diào)節(jié)網(wǎng)絡(luò)的均勻性，從而在面對隨機(jī)攻擊和特定攻擊時，提高網(wǎng)絡(luò)的魯棒性。因?yàn)槎鄶?shù)節(jié)點(diǎn)的度很少，少數(shù)節(jié)點(diǎn)的度很高，所以對那些度很高的節(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)符合這個關(guān)系式的網(wǎng)絡(luò)就是具有冪律特性的拓?fù)洹?/p>

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

定義4 網(wǎng)絡(luò)G中節(jié)點(diǎn)服從冪律分布，但是其缺少一個描述問題的特征尺度，所以被稱為無尺度網(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ò)中一個熱節(jié)點(diǎn)與鄰居節(jié)點(diǎn)組成的一個小規(guī)模網(wǎng)絡(luò)為整個網(wǎng)絡(luò)中的一個簇，這個熱節(jié)點(diǎn)是這個簇的簇頭CH[10]。與這些簇頭都相連的節(jié)點(diǎn)稱為匯聚節(jié)點(diǎn)。

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

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

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

普通節(jié)點(diǎn)的作用是存儲和收發(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)定的能源，而且，位置相對固定。

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

(1)增長特性：每一個時間段，有一個新的節(jié)點(diǎn)將會加入到網(wǎng)絡(luò)中，并與網(wǎng)絡(luò)中m個其他節(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個時間段后，得到N=t+m0個節(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)的度和吸附性決定加入哪個簇，并通知該熱節(jié)點(diǎn)。當(dāng)熱節(jié)點(diǎn)接收到所有加入信息后，會產(chǎn)生一個TDMA信號，并通知所有普通節(jié)點(diǎn)，普通節(jié)點(diǎn)將自己簇的簇頭信息存儲起來，這樣，簇頭和普通節(jié)點(diǎn)之間的通信就建立起來了。

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

2 數(shù)值分析

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

(4)

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

(5)

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

(6)

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

(7)

(8)

(9)

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

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

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)將自動取消此次轉(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號，根據(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],計算出此次轉(zhuǎn)發(fā)數(shù)據(jù)的最短路徑，然后將計算出最短路徑的路由表存儲到簇首的緩存中，并且另外通知此最短路徑中的節(jié)點(diǎn)[13]。

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

①任意兩個屬于不同簇的節(jié)點(diǎn)s和p之間的距離：近似為這兩個節(jié)點(diǎn)到各自簇中心節(jié)點(diǎn)的距離與這兩個簇中心節(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或受到攻擊無用時，網(wǎng)絡(luò)中的其他節(jié)點(diǎn)仍然能夠保持正常通信，網(wǎng)絡(luò)的結(jié)構(gòu)和性能仍然能夠維持基本穩(wěn)定的性質(zhì)。而路由魯棒性[14]則是代表該路由算法在遇到一些自身或外在不可控因素時的適應(yīng)能力。它是在節(jié)點(diǎn)能量、通信能力和網(wǎng)絡(luò)拓?fù)涞纫蛩刈饔孟碌暮暧^效應(yīng)。所以，路由魯棒性是評價路由算法優(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面對隨機(jī)攻擊具有很強(qiáng)的魯棒性[15]，但熱節(jié)點(diǎn)面對蓄意攻擊時又具有相對的脆弱性，所以熱節(jié)點(diǎn)的失效必定會影響無線傳感器網(wǎng)絡(luò)的通信質(zhì)量。

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

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

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

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

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

4.1 仿真環(huán)境

監(jiān)測區(qū)域大小為200m×200m的正方形范圍，共有無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)2000個，基站坐標(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)

為了評價SFRA路由算法的性能，對無線傳感器網(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)測區(qū)域內(nèi)進(jìn)行數(shù)據(jù)包傳送，網(wǎng)絡(luò)節(jié)點(diǎn)通過最短路徑算法進(jìn)行傳輸數(shù)據(jù)，降低了節(jié)點(diǎn)的能耗和丟包率，所以，傳輸路徑越短，跳數(shù)越少，時間就越短。該參數(shù)反映網(wǎng)絡(luò)的傳輸能力，傳輸數(shù)據(jù)包越多，說明傳輸能力越強(qiáng)。網(wǎng)絡(luò)能耗，即整個網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗情況。熱節(jié)點(diǎn)的能源供給較為固定，而普通節(jié)點(diǎn)的能源相對較小，所以，數(shù)量眾多的普通節(jié)點(diǎn)的能量消耗越小，網(wǎng)絡(luò)生存時間越長，節(jié)能效果越好。網(wǎng)絡(luò)生命周期就是網(wǎng)絡(luò)的生存時間，即網(wǎng)絡(luò)仍然存在最大連通子圖，網(wǎng)絡(luò)能夠正常通信的時間越長，網(wǎng)絡(luò)生存時間就越長。在仿真環(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)個數(shù)為n0=5，每次引入新節(jié)點(diǎn)時新生成的邊數(shù)m=5，網(wǎng)絡(luò)規(guī)模N=130。實(shí)驗(yàn)后該網(wǎng)絡(luò)圖的聚類系數(shù)為0.15，平均路徑長度為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)在雙對數(shù)坐標(biāo)下誤差允許范圍內(nèi)服從冪律分布，與上一節(jié)進(jìn)行的理論推導(dǎo)結(jié)果相一致，驗(yàn)證了其正確性。

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

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

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

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

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

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

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

4.4 仿真評價

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

4.4.1 總體性能評價

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

表1 四種路由算法的總體性能評價

4.4.2 路由可靠性評價

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

表2 四種路由算法的可靠性評價 %

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

無標(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)也是相對隨機(jī)，平均連接度為4。表3為四種路由算法的網(wǎng)絡(luò)節(jié)點(diǎn)度分布。

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

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

5 結(jié)束語

研究了一種基于無標(biāo)度拓?fù)涮匦缘臒o線傳感器網(wǎng)絡(luò)路由算法。將無標(biāo)度理論應(yīng)用到無線傳感器網(wǎng)絡(luò)的路由算法研究中，并針對無標(biāo)度特殊的拓?fù)浣Y(jié)構(gòu)，采用CDZ算法計算數(shù)據(jù)傳輸最短路徑。大量仿真實(shí)驗(yàn)表明，該算法在降低傳感器網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生命周期等方面比傳統(tǒng)無線傳感器網(wǎng)絡(luò)路由算法有較大優(yōu)勢，可應(yīng)用于無線傳感器網(wǎng)絡(luò)中，并對無線傳感器網(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ī)系統(tǒng),2014(3):448-452.

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

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

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

[7]文宏,樊曉平,張會福,等.無標(biāo)度網(wǎng)絡(luò)局部路由算法優(yōu)化與設(shè)計[J].湖南大學(xué)學(xué)報:自然科學(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ī)工程,2006,32(14):87-88.

[12]唐晉韜,王挺,王戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報,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

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

礎(chǔ)研究計劃資助項(xiàng)目(F13-316-1-22)；沈陽理工大學(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