一種基于無標(biāo)度局域世界演化網(wǎng)絡(luò)模型的無線傳感器網(wǎng)絡(luò)拓?fù)錁?gòu)建

北京信息科技大學(xué) 自動化學(xué)院，北京 100192

一、引言

1999年，Barabasi與Albert在研究萬維網(wǎng)的度分布時(shí)發(fā)現(xiàn)，網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布并不符合泊松分布關(guān)系，而是符合一種冪律分布，即隨著節(jié)點(diǎn)連接度的增加，其概率呈不斷遞減的規(guī)律，于是提出BA無標(biāo)度網(wǎng)絡(luò)模型。該模型的拓?fù)溲莼伞霸鲩L”和“擇優(yōu)連接”兩個(gè)機(jī)制完成，所形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相較于復(fù)雜網(wǎng)絡(luò)中規(guī)則網(wǎng)絡(luò)模型和隨機(jī)網(wǎng)絡(luò)模型更具有現(xiàn)實(shí)意義，符合現(xiàn)實(shí)世界中大多數(shù)網(wǎng)絡(luò)的結(jié)構(gòu)，更加便于對復(fù)雜網(wǎng)絡(luò)的研究[1-3]。

此后，各學(xué)者著手在其基礎(chǔ)上做了各種各樣的擴(kuò)展[4]。Bianconi等人[5]提出適應(yīng)度模型，在優(yōu)先連接的過程中，新加入網(wǎng)絡(luò)的節(jié)點(diǎn)優(yōu)先連接的概率并非是與節(jié)點(diǎn)的度成正比，而是與節(jié)點(diǎn)度和適應(yīng)度的乘積成正比。Zhu等人[6]考慮無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）中節(jié)點(diǎn)能量損耗過快的問題，提出能量感知演化模型（Energy-Aware Evolution Model，EAEM），對適應(yīng)度模型進(jìn)行優(yōu)化，將節(jié)點(diǎn)剩余能量作為適應(yīng)度，進(jìn)行擇優(yōu)連接時(shí)的概率計(jì)算。Barrat等人[7]提出一種加權(quán)網(wǎng)絡(luò)模型——BBV模型，將節(jié)點(diǎn)的權(quán)重考慮進(jìn)無標(biāo)度網(wǎng)絡(luò)模型中。李翔等人[8]根據(jù)某些網(wǎng)絡(luò)的特點(diǎn)，提出局域世界演化網(wǎng)絡(luò)模型，在新加入節(jié)點(diǎn)優(yōu)先連接時(shí)，不是選擇網(wǎng)絡(luò)中原有舊節(jié)點(diǎn)作為備選范圍，而是在舊節(jié)點(diǎn)中隨機(jī)選擇若干個(gè)節(jié)點(diǎn)，縮小了可連接節(jié)點(diǎn)的范圍。張燕平等人[9]提出局域世界刪除演化網(wǎng)絡(luò)模型，論述了刪除部分節(jié)點(diǎn)和邊對現(xiàn)有網(wǎng)絡(luò)的影響。羅小娟等人[10]從局域世界演化角度出發(fā)，提出了一種能量感知的局域世界動態(tài)演化模型，不僅考慮了傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量感知連接機(jī)制，還考慮了節(jié)點(diǎn)和鏈路在演化過程中的動態(tài)變化。

韓濤[11]提出了無標(biāo)度網(wǎng)絡(luò)路徑能耗優(yōu)化模型，并指出節(jié)點(diǎn)通訊能耗與平均路徑長度成正比。在模型仿真模擬中，平均路徑能耗最低時(shí)，網(wǎng)絡(luò)中最優(yōu)節(jié)點(diǎn)度為10，即每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度值閾值為10。本文參照其結(jié)論，對傳統(tǒng)的局域世界演化網(wǎng)絡(luò)模型進(jìn)行優(yōu)化，旨在降低網(wǎng)絡(luò)平均最短路徑，以達(dá)到降低能耗，延長網(wǎng)絡(luò)生存周期，提高抗毀性的目的。

二、無標(biāo)度網(wǎng)絡(luò)及特征參數(shù)

1、無標(biāo)度網(wǎng)絡(luò)BA模型

Barabasi和Albert研究萬維網(wǎng)的度分布，漸漸發(fā)覺萬維網(wǎng)網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布不符合泊松分布，而是符合一種冪律分布，即隨著節(jié)點(diǎn)度的增加，節(jié)點(diǎn)度的概率呈不斷遞減的趨勢，于是提出BA無標(biāo)度網(wǎng)絡(luò)模型，其網(wǎng)絡(luò)模型有兩個(gè)重要特性：

（1）增長：網(wǎng)絡(luò)在每一個(gè)時(shí)間步都會加入新節(jié)點(diǎn)，通過新加入的節(jié)點(diǎn)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的動態(tài)變化；

（2）擇優(yōu)連接：新增的節(jié)點(diǎn)與原網(wǎng)絡(luò)中節(jié)點(diǎn)度大的節(jié)點(diǎn)連接的概率大。

基于網(wǎng)絡(luò)的增長和優(yōu)先連接特性，BA無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法如下：

（1）增長：從一個(gè)具有m0個(gè)節(jié)點(diǎn)的初始網(wǎng)絡(luò)開始，每次加入一個(gè)新的節(jié)點(diǎn)，并且與網(wǎng)絡(luò)中m個(gè)已存在的節(jié)點(diǎn)相連接，在這里m≤m0；

（2）優(yōu)先連接：一個(gè)新節(jié)點(diǎn)j與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率Πi為：

其中，ki—已存在節(jié)點(diǎn)i的度；

kj—新節(jié)點(diǎn)j的度。

在經(jīng)過時(shí)間步t后，該算法會產(chǎn)生一個(gè)有N=t+m0個(gè)節(jié)點(diǎn)、mt條邊的網(wǎng)絡(luò)。圖1為當(dāng)m=m0=2時(shí)的BA網(wǎng)絡(luò)的演化過程。初始網(wǎng)絡(luò)有兩個(gè)原節(jié)點(diǎn)，每個(gè)時(shí)間步新增加的一個(gè)節(jié)點(diǎn)按優(yōu)先連接機(jī)制與網(wǎng)絡(luò)中已存在的兩個(gè)節(jié)點(diǎn)度值大的節(jié)點(diǎn)相連。需要注意的是，在算法中，每個(gè)舊節(jié)點(diǎn)都有一個(gè)概率，而新節(jié)點(diǎn)選擇是否連接舊節(jié)點(diǎn)，需要看隨機(jī)數(shù)落在哪個(gè)節(jié)點(diǎn)的概率范圍內(nèi)。

平均路徑長度[12]：網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)i和j之間的距離dij定義為連接這兩個(gè)節(jié)點(diǎn)的最短路徑上的跳數(shù)。網(wǎng)絡(luò)的平均路徑長度L定義為任意兩個(gè)節(jié)點(diǎn)之間的最短路徑數(shù)之和的平均值，即：

其中，N—網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。

聚類系數(shù)[12]：若網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i與ki個(gè)節(jié)點(diǎn)直接相連，這ki個(gè)節(jié)點(diǎn)就稱為節(jié)點(diǎn)i的鄰居。由數(shù)學(xué)分析知，在這ki個(gè)節(jié)點(diǎn)之間最多可能有ki(ki-1)/2條邊，而這ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)和總的可能的邊數(shù)之比就定義為節(jié)點(diǎn)i的聚類系數(shù)Ci，即：

其中，Ei—ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)。

2、無標(biāo)度網(wǎng)絡(luò)局域世界演化網(wǎng)絡(luò)模型

在BA無標(biāo)度網(wǎng)絡(luò)中，僅僅依賴各節(jié)點(diǎn)的度值來計(jì)算每一個(gè)節(jié)點(diǎn)的優(yōu)先連接概率，由此可得到網(wǎng)絡(luò)冪律形式的節(jié)點(diǎn)度分布。但在許多現(xiàn)實(shí)的網(wǎng)絡(luò)中，局域世界連接性的存在，每一個(gè)節(jié)點(diǎn)都有各自的關(guān)系網(wǎng)，因而各節(jié)點(diǎn)也只能使用整個(gè)網(wǎng)絡(luò)中局域關(guān)系網(wǎng)所連接的信息。李翔等人[8]提出一種局域世界演化網(wǎng)絡(luò)模型來描述此種情況。模型構(gòu)造算法如下：

（1）增長：網(wǎng)絡(luò)初始時(shí)有m0個(gè)原始節(jié)點(diǎn)和e0條邊，每個(gè)時(shí)間步新加入一個(gè)節(jié)點(diǎn)和附帶的m條邊；

（2）局域世界優(yōu)先連接：從網(wǎng)絡(luò)已有的節(jié)點(diǎn)中隨機(jī)選取M個(gè)節(jié)點(diǎn)（M≥m），作為新加入節(jié)點(diǎn)的局域世界關(guān)系網(wǎng)。新加入的節(jié)點(diǎn)根據(jù)下面的優(yōu)先連接概率來選擇與局域世界關(guān)系網(wǎng)中的m個(gè)節(jié)點(diǎn)相連：

其中，LW—新選的M個(gè)節(jié)點(diǎn)組成的局域世界。

三、基于無標(biāo)度局域世界演化模型的WSN網(wǎng)絡(luò)拓?fù)?/h2>

1、基于WSN的局域世界演化網(wǎng)絡(luò)模型構(gòu)造算法

從局域世界演化網(wǎng)絡(luò)模型出發(fā)，結(jié)合傳感器網(wǎng)絡(luò)的特點(diǎn)，對傳統(tǒng)的無標(biāo)度局域世界演化網(wǎng)絡(luò)模型進(jìn)行優(yōu)化。一個(gè)是在WSN中，每個(gè)節(jié)點(diǎn)都有其通訊半徑，在增長的過程中，不能選取通訊范圍外的節(jié)點(diǎn)進(jìn)行連接；另一個(gè)是，在WSN優(yōu)化中，考慮到網(wǎng)絡(luò)中部分節(jié)點(diǎn)連接度過高，會影響整個(gè)網(wǎng)絡(luò)的能量平衡性及抗毀性[11]，設(shè)定網(wǎng)絡(luò)中節(jié)點(diǎn)度值閾值kmax≤10。該模型構(gòu)造算法如下：

（1）增長：網(wǎng)絡(luò)初始時(shí)有m0個(gè)原節(jié)點(diǎn)，每個(gè)時(shí)間步新加入一個(gè)節(jié)點(diǎn)和附帶的m條邊；

（2）改進(jìn)的局域世界優(yōu)先連接。選取新節(jié)點(diǎn)通訊范圍（半徑為r的圓形區(qū)域）內(nèi)的M個(gè)節(jié)點(diǎn)（M≥m），作為新加入節(jié)點(diǎn)的局域世界。新加入網(wǎng)絡(luò)的節(jié)點(diǎn)根據(jù)以下優(yōu)先連接概率來選擇與規(guī)定局域世界中的m個(gè)節(jié)點(diǎn)相連：

其中，S—由局域世界中（即新節(jié)點(diǎn)通訊范圍內(nèi)）隨機(jī)選取的M個(gè)節(jié)點(diǎn)組成。

在新節(jié)點(diǎn)擇優(yōu)連接過程中，若將要連接的節(jié)點(diǎn)度=10，則新節(jié)點(diǎn)選取概率第二大的節(jié)點(diǎn)繼續(xù)判斷，直到找到符合節(jié)點(diǎn)度≤9的節(jié)點(diǎn)，才與之連接。具體流程如圖2所示。

2、仿真及分析

（1）仿真設(shè)計(jì)

仿真環(huán)境設(shè)定：

面積：100m×100m的方形區(qū)域；

網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)m0：5（這里使初始節(jié)點(diǎn)間全連通）；

新增節(jié)點(diǎn)添加新邊數(shù)m：1；

節(jié)點(diǎn)總數(shù)N：50；

節(jié)點(diǎn)通訊半徑r：50m；

局域世界所選取的節(jié)點(diǎn)數(shù)M：5。

仿真結(jié)果如圖3、圖4所示。

（2）結(jié)果分析

在本次仿真環(huán)境下進(jìn)行了10次實(shí)驗(yàn)，圖3～5為首次仿真結(jié)果圖，表1為 模型優(yōu)化前后網(wǎng)絡(luò)的平均路徑長度和聚類系數(shù)比較。多次進(jìn)行仿真實(shí)驗(yàn)是為了證明優(yōu)化模型的適用性、普遍性。

圖3和圖4是模型優(yōu)化前后的網(wǎng)絡(luò)拓?fù)鋱D，在仿真中，考慮現(xiàn)實(shí)場景下隨機(jī)拋撒節(jié)點(diǎn)位置的不確定性，為了使新增節(jié)點(diǎn)在增長及擇優(yōu)連接的過程中可以找到符合條件的舊節(jié)點(diǎn)相連接，增大程序的可實(shí)現(xiàn)性，在不改變網(wǎng)絡(luò)其他參數(shù)的前提下，適當(dāng)增大節(jié)點(diǎn)通訊半徑（一般設(shè)置節(jié)點(diǎn)通訊半徑不超過區(qū)域邊長的一半）。從圖4中可以直觀地看出，優(yōu)化的模型較之圖3中局域世界網(wǎng)絡(luò)演化模型，節(jié)點(diǎn)間連邊密度小，距離短。

圖5給出優(yōu)化的模型中各節(jié)點(diǎn)的度值大小，可以看出，仿真中各節(jié)點(diǎn)的度均未超過設(shè)定閾值。當(dāng)網(wǎng)絡(luò)規(guī)模較小，即節(jié)點(diǎn)總數(shù)較少時(shí)，模型優(yōu)化前后的各節(jié)點(diǎn)度大小分布差別不大，因?yàn)樵趦?yōu)化的模型中規(guī)定單個(gè)節(jié)點(diǎn)度的上限值不超過10，而網(wǎng)絡(luò)中新增節(jié)點(diǎn)只增加一條邊，從概率角度來講，節(jié)點(diǎn)度值超過10的節(jié)點(diǎn)也很少。也就是說，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，優(yōu)化的模型在設(shè)定節(jié)點(diǎn)度值閾值方面的效用比較小。

根據(jù)尹文曉[13]構(gòu)建的網(wǎng)絡(luò)生命周期模型，網(wǎng)絡(luò)生命周期Tnet為：

其中，Ei—節(jié)點(diǎn)的剩余能量；

L—平均路徑長度；

δ(0) —負(fù)載量（具體可查詢文獻(xiàn)[13]）；

a、b—常量。

從公式中可以看出，當(dāng)其他參數(shù)不變時(shí)，網(wǎng)絡(luò)的平均路徑最短長度L和節(jié)點(diǎn)生命周期Tnet的關(guān)系，即平均路徑最短長度L越小，節(jié)點(diǎn)生命周期Ti越長。

由此，本文優(yōu)化的模型旨在減小網(wǎng)絡(luò)的平均最短路徑長度，從而延長網(wǎng)絡(luò)的生命周期，間接提高網(wǎng)絡(luò)的抗毀性。

由表1可看出，仿真結(jié)果中，10次有7次優(yōu)化后的模型平均最短路徑比傳統(tǒng)的局域世界演化網(wǎng)絡(luò)模型小。因?yàn)樗惴ㄖ芯W(wǎng)絡(luò)節(jié)點(diǎn)生成位置的隨機(jī)性，造成少許情況下優(yōu)化的網(wǎng)絡(luò)模型中，部分新節(jié)點(diǎn)連接通訊范圍內(nèi)較遠(yuǎn)的節(jié)點(diǎn)，而傳統(tǒng)網(wǎng)絡(luò)中部分新節(jié)點(diǎn)連接范圍內(nèi)較近的節(jié)點(diǎn)，使得之后增長的過程中，網(wǎng)絡(luò)整體平均最短路徑增大。但在大部分情況下，優(yōu)化的模型仍能有效降低網(wǎng)絡(luò)的平均最短路徑長度，達(dá)到提高網(wǎng)絡(luò)抗毀性的目的。

表1 模型優(yōu)化前后網(wǎng)絡(luò)的平均路徑長度和聚類系數(shù)比較

四、結(jié)束語

無標(biāo)度網(wǎng)絡(luò)抗毀性方法一直都是傳感器網(wǎng)絡(luò)抗毀性領(lǐng)域研究的重點(diǎn)。本文從無標(biāo)度局域世界演化網(wǎng)絡(luò)模型入手，結(jié)合傳感器網(wǎng)絡(luò)的特點(diǎn)，對局域世界演化網(wǎng)絡(luò)模型進(jìn)行改進(jìn)優(yōu)化。通過matlab仿真平臺，分析對比傳統(tǒng)的局域世界演化網(wǎng)絡(luò)模型和改進(jìn)的網(wǎng)絡(luò)模型，其結(jié)果證明，該模型可有效降低網(wǎng)絡(luò)平均最短路徑，驗(yàn)證了模型的真實(shí)有效性，對網(wǎng)絡(luò)抗毀性方法有借鑒意義。