王傳云，朱 濤，尹 燕，趙軍輝,3

(1.華東交通大學(xué) 信息工程學(xué)院,江西 南昌 330013;2.華東交通大學(xué) 軟件學(xué)院,江西 南昌330013;3.北京交通大學(xué) 電子與信息工程學(xué)院，北京 100044)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是由大量具有計(jì)算和通信能力的傳感器節(jié)點(diǎn)組成，一般部署在無(wú)人值守區(qū)域，用以自主完成指定的任務(wù)[1]。近些年，復(fù)雜網(wǎng)絡(luò)理論已成為跨學(xué)科領(lǐng)域的重要分析工具和研究方法[2～4]。隨著研究的不斷深入，發(fā)現(xiàn)WSNs的很多特性及行為符合復(fù)雜網(wǎng)絡(luò)的基本機(jī)制，因此，通過(guò)復(fù)雜網(wǎng)絡(luò)研究WSNs演化模型已經(jīng)成為當(dāng)前研究的一個(gè)重要熱點(diǎn)[5]。

2004年，BBV加權(quán)演化網(wǎng)絡(luò)模型被提出，模型考慮了拓?fù)浜蜋?quán)重在演化過(guò)程中的關(guān)系，重現(xiàn)出了真實(shí)網(wǎng)絡(luò)情況[6]。文獻(xiàn)[7]結(jié)合差額獎(jiǎng)懲機(jī)制，提出了基于獎(jiǎng)懲機(jī)制的信任演化模型，解決了WSNs節(jié)點(diǎn)間信任決策導(dǎo)致網(wǎng)絡(luò)不穩(wěn)定的問(wèn)題。文獻(xiàn)[8]考慮節(jié)點(diǎn)的強(qiáng)度和節(jié)點(diǎn)的吸引力，提出了基于節(jié)點(diǎn)適應(yīng)度動(dòng)態(tài)演化的加權(quán)復(fù)雜網(wǎng)絡(luò)演化模型。在復(fù)雜網(wǎng)絡(luò)演化模型基礎(chǔ)上，將WSNs與演化模型相結(jié)合，文獻(xiàn)[9]結(jié)合復(fù)雜網(wǎng)絡(luò)分析了WSNs的拓?fù)涮卣骱痛嗳跣詫?duì)于節(jié)點(diǎn)能耗優(yōu)化和網(wǎng)絡(luò)生命周期的影響。文獻(xiàn)[10]結(jié)合了節(jié)點(diǎn)剩余能量、信號(hào)強(qiáng)度和鏈路質(zhì)量提出了能耗均衡路由協(xié)議，很好地均衡網(wǎng)絡(luò)中的能量。文獻(xiàn)[11]中根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路數(shù)量增加和減少的動(dòng)態(tài)性，結(jié)合復(fù)雜網(wǎng)絡(luò)模型，提出了高效動(dòng)態(tài)自組織演化模型，使整個(gè)WSNs的能量消耗更加平衡，擁有更好的隨機(jī)節(jié)點(diǎn)容錯(cuò)性。由于網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)的權(quán)重沒(méi)有進(jìn)行限制，使得節(jié)點(diǎn)權(quán)重可以無(wú)限制增長(zhǎng)。文獻(xiàn)[12]結(jié)合加權(quán)演化動(dòng)力學(xué)理論提出了權(quán)重強(qiáng)度約束加權(quán)演化模型，限制了節(jié)點(diǎn)強(qiáng)度的無(wú)限增加，可以平衡網(wǎng)絡(luò)的流量負(fù)擔(dān)，降低節(jié)點(diǎn)快速死亡的風(fēng)險(xiǎn)。文獻(xiàn)[13]提出了基于雙向吸引機(jī)制的WSNs拓?fù)淇刂扑惴?，使得WSNs的成簇特性明顯，構(gòu)建層次型拓?fù)浣Y(jié)構(gòu)，為構(gòu)建大規(guī)模的WSNs分簇拓?fù)浣Y(jié)構(gòu)提供參考。

本文在權(quán)重約束模型的基礎(chǔ)上進(jìn)行改進(jìn)，結(jié)合優(yōu)化的雙向選擇機(jī)制，提出了點(diǎn)權(quán)約束釋放模型。利用MATLAB工具，對(duì)模型的簇頭分布、點(diǎn)權(quán)分布、度分布和網(wǎng)絡(luò)能耗進(jìn)行仿真，仿真結(jié)果和理論分析相吻合，驗(yàn)證了理論的正確性。

1 基礎(chǔ)理論

1.1 WSNs分簇拓?fù)浣Y(jié)構(gòu)

在分簇拓?fù)浣Y(jié)構(gòu)中，對(duì)節(jié)點(diǎn)進(jìn)行分類(lèi)，分為簇頭節(jié)點(diǎn)和普通節(jié)點(diǎn)。普通節(jié)點(diǎn)負(fù)責(zé)收集信息，將信息發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)將信息匯總再發(fā)送給基站。在WSNs中，分簇拓?fù)浣Y(jié)構(gòu)可以有效減少能量損耗，延長(zhǎng)網(wǎng)絡(luò)節(jié)點(diǎn)的壽命。同時(shí)，分簇拓?fù)浣Y(jié)構(gòu)具有可延展性，可以應(yīng)用到大規(guī)模復(fù)雜WSNs中，降低網(wǎng)絡(luò)通信負(fù)擔(dān)。

1.2 權(quán)重約束演化模型

BBV加權(quán)演化網(wǎng)絡(luò)模型中，當(dāng)節(jié)點(diǎn)邊緣權(quán)重增加時(shí)，將導(dǎo)致節(jié)點(diǎn)權(quán)重的增加。BBV模型中，新加入節(jié)點(diǎn)(以下簡(jiǎn)稱新節(jié)點(diǎn))連接已存在節(jié)點(diǎn)(以下簡(jiǎn)稱老節(jié)點(diǎn))的概率為p=si/∑ksk，從連接概率公式可以看出，節(jié)點(diǎn)i的點(diǎn)權(quán)越大，連接的概率也就越大，導(dǎo)致節(jié)點(diǎn)i的點(diǎn)權(quán)有無(wú)限增大的可能；權(quán)重約束模型中，給點(diǎn)權(quán)設(shè)置最大閾值smax，限制節(jié)點(diǎn)權(quán)重的無(wú)限增長(zhǎng)，達(dá)到降低能量損耗的作用[12]。

2 基于雙向選擇機(jī)制的點(diǎn)權(quán)約束釋放演化模型

2.1 算法前提假設(shè)

假設(shè)WSNs中節(jié)點(diǎn)隨機(jī)分布，并具備以下特點(diǎn)：1)每個(gè)傳感器節(jié)點(diǎn)都有自己唯一的標(biāo)識(shí)符ID；2)每個(gè)傳感器節(jié)點(diǎn)在部署時(shí)都具有相同的能量，且能量不能被補(bǔ)充；3)基站的能量充足，且可以檢測(cè)到WSNs區(qū)域的內(nèi)部或外部。

2.2 雙向選擇機(jī)制下權(quán)重約束的WSNs拓?fù)溲莼Ｐ?/h3>

本模型采用權(quán)重約束模型中的方法，給節(jié)點(diǎn)的權(quán)重設(shè)置最大閾值smax[12]。網(wǎng)絡(luò)的演化步驟如下：

1)新節(jié)點(diǎn)的加入：每一個(gè)時(shí)間步加入一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)與m個(gè)老節(jié)點(diǎn)以一定概率連接,連接概率見(jiàn)式(1)和式(2)，新節(jié)點(diǎn)建立連邊后，將邊權(quán)值賦為w0

(1)

(2)

式中p(i←j)為節(jié)點(diǎn)j連接到節(jié)點(diǎn)i的概率，此處，i為老節(jié)點(diǎn)，j為新節(jié)點(diǎn)，si為節(jié)點(diǎn)i的權(quán)重，smax為節(jié)點(diǎn)權(quán)重的最大閾值，β為權(quán)重超過(guò)smax時(shí)，設(shè)置的si/smax固定數(shù)值，起到固定連接概率的作用，∑ksk(1-sk/smax)(k=1，2，…，N)為網(wǎng)絡(luò)中已存在節(jié)點(diǎn)的權(quán)重總和。

2)老節(jié)點(diǎn)間相互連接及邊權(quán)的更新：每一個(gè)時(shí)間步以概率α在網(wǎng)絡(luò)已存在的節(jié)點(diǎn)中，增加n條新連接[14]。選擇兩個(gè)老節(jié)點(diǎn)i,j以式(1)、式(2)的連接概率進(jìn)行連接，如果兩個(gè)節(jié)點(diǎn)未建立連接，則建立連接，并將邊權(quán)值賦為w0；如果已經(jīng)建立連接，則將其邊權(quán)值增加Δw。

在模型演化過(guò)程中，初始階段本模型和一般演化模型類(lèi)似，節(jié)點(diǎn)強(qiáng)度應(yīng)遠(yuǎn)小于smax，si/smax≈0。隨著時(shí)間的增加，節(jié)點(diǎn)連邊數(shù)逐漸增加，會(huì)出現(xiàn)點(diǎn)權(quán)較大的節(jié)點(diǎn)。這時(shí)，通過(guò)smax的限制，可以降低該節(jié)點(diǎn)被連接的概率，使點(diǎn)權(quán)緩慢增加或停止增長(zhǎng)。但是，在大規(guī)模WSNs中，會(huì)出現(xiàn)大量節(jié)點(diǎn)的點(diǎn)權(quán)達(dá)到smax，這會(huì)導(dǎo)致大量老節(jié)點(diǎn)無(wú)法連接新節(jié)點(diǎn)。使得在新節(jié)點(diǎn)加入時(shí)，新節(jié)點(diǎn)遠(yuǎn)距離連接其他節(jié)點(diǎn)，節(jié)點(diǎn)能量過(guò)多的消耗，所以在點(diǎn)權(quán)達(dá)到smax時(shí)，將si/smax替換成β，使得連接概率固定，這樣新節(jié)點(diǎn)可以就近連接點(diǎn)權(quán)達(dá)到smax的老節(jié)點(diǎn)。

下面，本文將推導(dǎo)在節(jié)點(diǎn)權(quán)重si

(3)

內(nèi)部老節(jié)點(diǎn)連邊的方程為

(4)

式中Wij為兩個(gè)節(jié)點(diǎn)i，j的邊權(quán)，m為新節(jié)點(diǎn)連接老節(jié)點(diǎn)的個(gè)數(shù)，α為每個(gè)時(shí)間步老節(jié)點(diǎn)間新增連邊的概率，n為老節(jié)點(diǎn)新增連邊的個(gè)數(shù)。

點(diǎn)權(quán)的變化由內(nèi)部老節(jié)點(diǎn)的連接和權(quán)重的更新以及新節(jié)點(diǎn)的加入引起，因此節(jié)點(diǎn)i權(quán)重的變化率方程為

(5)

由于大多數(shù)節(jié)點(diǎn)的權(quán)重遠(yuǎn)小于smax，因此近似得到了權(quán)重的總和

∑ksk(1-sk/smax)≈∑ksk=(m2+2n)t

(6)

將式(6)代入式(5)中，可以得到

(7)

將式(7)積分，并代入初始條件si(t=ti)=m求解，可得點(diǎn)權(quán)si隨時(shí)間t變化的方程

(8)

從式(8)中可以看到，在si

點(diǎn)權(quán)si的概率可以通過(guò)式(9)計(jì)算

(9)

由于新節(jié)點(diǎn)以固定時(shí)間步加入網(wǎng)絡(luò)，其遵循均勻分布。將p(ti)=1/t代入式(9)計(jì)算得到節(jié)點(diǎn)權(quán)重概率分布公式

(10)

由式(10)可以看出：si

(11)

(12)

由于此時(shí)新節(jié)點(diǎn)加入和老節(jié)點(diǎn)連邊的情況較多，不能對(duì)公式進(jìn)行統(tǒng)一推導(dǎo)，所以當(dāng)新節(jié)點(diǎn)連接權(quán)重達(dá)到smax的老節(jié)點(diǎn)或者老節(jié)點(diǎn)權(quán)重一個(gè)達(dá)到smax，一個(gè)未達(dá)到smax時(shí)，使用式(11)進(jìn)行計(jì)算；當(dāng)兩個(gè)老節(jié)點(diǎn)權(quán)重均達(dá)到smax時(shí)，使用式(12)進(jìn)行計(jì)算。

2.3 算法步驟

1)初始網(wǎng)絡(luò)：給定m0個(gè)初始節(jié)點(diǎn)，初始節(jié)點(diǎn)間兩兩連接，邊權(quán)賦值為w0。

2)網(wǎng)絡(luò)增長(zhǎng)：依照雙向選擇機(jī)制，每個(gè)時(shí)間步加入一個(gè)新節(jié)點(diǎn)，以式(1)、式(2)的連接概率進(jìn)行連接。同時(shí)，以概率α對(duì)老節(jié)點(diǎn)邊權(quán)進(jìn)行更新。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)達(dá)到N時(shí)，網(wǎng)絡(luò)停止增長(zhǎng)。

3)簇群形成：根據(jù)預(yù)設(shè)簇頭數(shù)目，按照點(diǎn)權(quán)si的大小依次選取簇頭，簇頭通信半徑范圍內(nèi)的其他節(jié)點(diǎn)，依照節(jié)點(diǎn)與簇頭間的距離大小來(lái)選擇相應(yīng)的簇頭節(jié)點(diǎn)，加入簇群。簇群完成后，每個(gè)簇頭節(jié)點(diǎn)將自身ID廣播至與其相連的節(jié)點(diǎn)，普通節(jié)點(diǎn)將自身ID發(fā)送給簇頭節(jié)點(diǎn)并儲(chǔ)存。

4)信息傳輸：節(jié)點(diǎn)信息傳輸時(shí)，普通節(jié)點(diǎn)將信息發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)將信息發(fā)送給基站；遠(yuǎn)離基站的簇頭選擇其他簇群的簇頭作為中繼節(jié)點(diǎn)，對(duì)信息進(jìn)行多跳傳輸，以減少能量損耗。

3 模型仿真與結(jié)果分析

本文利用MATLAB 2016b仿真工具，模型仿真場(chǎng)景為1 000 m×1 000 m，網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為1 000，節(jié)點(diǎn)隨機(jī)分布，網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)m0=8，節(jié)點(diǎn)通信半徑為80，每個(gè)新節(jié)點(diǎn)連接m=6個(gè)老節(jié)點(diǎn)，最大閾值smax=100，超出smax時(shí)si/smax的固定數(shù)值β=0.9，每個(gè)時(shí)間步老節(jié)點(diǎn)間新增連邊的概率α=0.8，各邊初始權(quán)重和增加權(quán)重w0=Δw=1。在本節(jié)中，將本文模型與雙向選擇模型和權(quán)重約束模型進(jìn)行對(duì)比。通過(guò)四個(gè)方面比較這三個(gè)模型：簇頭分布、點(diǎn)權(quán)分布、度分布和網(wǎng)絡(luò)能耗。

圖1中，取不同的β=0.8，0.85，0.9，0.95對(duì)節(jié)點(diǎn)權(quán)重分布進(jìn)行比較。從仿真結(jié)果可以看出，隨著β的增長(zhǎng)，約束效果的增加，節(jié)點(diǎn)強(qiáng)度分布的尾端逐漸收縮。對(duì)比可以發(fā)現(xiàn)，當(dāng)β=0.8，0.85時(shí)，尾部收縮不明顯；當(dāng)β=0.9時(shí)，尾部收縮效果明顯；當(dāng)β=0.95，尾部收縮相對(duì)密集。因此，本文模型選擇β=0.9進(jìn)行網(wǎng)絡(luò)仿真。

圖1 本文模型中β=0.8，0.85，0.9，0.95的節(jié)點(diǎn)權(quán)重分布

本文選擇100個(gè)節(jié)點(diǎn)進(jìn)行模型仿真。如圖2所示，在雙向選擇模型中，會(huì)出現(xiàn)個(gè)別簇頭大量連接節(jié)點(diǎn)，導(dǎo)致其他簇頭連接節(jié)點(diǎn)過(guò)少的情況；而權(quán)重約束模型中簇頭節(jié)點(diǎn)分布不均，出現(xiàn)簇頭距離近的情況；而在本文模型中，簇頭節(jié)點(diǎn)分布均勻，簇內(nèi)節(jié)點(diǎn)也相對(duì)分布均勻。

圖2 100節(jié)點(diǎn)5簇頭模型仿真

從圖3可以看出，當(dāng)強(qiáng)度較小時(shí)，三個(gè)模型點(diǎn)權(quán)的分布基本上是一致的，但隨著權(quán)重的增長(zhǎng)，尾部明顯不同。在雙向選擇模型中，由于點(diǎn)權(quán)的無(wú)限增長(zhǎng)，導(dǎo)致一些節(jié)點(diǎn)的點(diǎn)權(quán)值接近104；同時(shí)，在權(quán)重約束模型中，由于點(diǎn)權(quán)被約束，尾部被限制在100左右；在本文的模型中，可以看到尾部的一些節(jié)點(diǎn)強(qiáng)度超出了smax，這是因?yàn)榻o達(dá)到smax的節(jié)點(diǎn)固定連接數(shù)值β的原因。這些超出smax的節(jié)點(diǎn)就可以繼續(xù)連接近距離新節(jié)點(diǎn)。

圖3 點(diǎn)權(quán)分布

如圖4所示，比較了節(jié)點(diǎn)的度分布，當(dāng)節(jié)點(diǎn)權(quán)重強(qiáng)度受到限制時(shí)，將影響其他節(jié)點(diǎn)的連接，但是，由于節(jié)點(diǎn)釋放的原因，所以可以清楚地看到度的分布的尾部會(huì)有一些節(jié)點(diǎn)擺脫約束。

圖4 度分布

圖5通過(guò)對(duì)1 000個(gè)節(jié)點(diǎn)的能耗仿真可以看出，三個(gè)模型第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)基本差不多。在雙向選擇模型和權(quán)重約束模型中系統(tǒng)能耗完全消耗分別在1 200輪和1 400輪左右。但是，本文模型中，在2 000輪時(shí)，系統(tǒng)中還有節(jié)點(diǎn)沒(méi)有死亡。這是因?yàn)楸疚哪Ｐ偷墓?jié)點(diǎn)受到約束，不會(huì)無(wú)限制點(diǎn)權(quán)增加；同時(shí)，在點(diǎn)權(quán)達(dá)到smax時(shí)，給予一定的選擇概率，使節(jié)點(diǎn)可以突破smax，避免了大量節(jié)點(diǎn)的點(diǎn)權(quán)達(dá)到smax不增長(zhǎng)的情況，為WSNs提供了相對(duì)均勻的簇頭分布。

圖5 三種模型的網(wǎng)絡(luò)能耗分析比較

4 結(jié) 論

本文在雙向選擇模型的基礎(chǔ)上增加老節(jié)點(diǎn)間連邊和邊權(quán)的更新，使模型更接近實(shí)際情況；通過(guò)對(duì)權(quán)重約束模型中點(diǎn)權(quán)約束的釋放，使被約束節(jié)點(diǎn)可以連接新節(jié)點(diǎn)，避免能量過(guò)多損耗。對(duì)該模型的簇頭分布、點(diǎn)權(quán)分布、度分布和網(wǎng)絡(luò)能耗4個(gè)方面進(jìn)行了仿真，結(jié)果表明：本文模型在簇頭分布上比較合理；在點(diǎn)權(quán)和度分布上有著很好的限制和釋放的效果。當(dāng)對(duì)比模型節(jié)點(diǎn)全部死亡時(shí)，本文模型的節(jié)點(diǎn)死亡僅達(dá)到80 %左右，在減少網(wǎng)絡(luò)能耗方面效果顯著，可以有效地延長(zhǎng)網(wǎng)絡(luò)中節(jié)點(diǎn)的壽命。而且，通過(guò)分簇拓?fù)浣Y(jié)構(gòu)可以將模型延展到大規(guī)模復(fù)雜傳感器網(wǎng)絡(luò)，使得該模型更適用于大規(guī)模WSNs場(chǎng)景。