基于最優(yōu)剛性子圖的勢博弈無線傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法

魏連鎖，韓 建，金 濤，蘇 揚(yáng)，郭 媛

(齊齊哈爾大學(xué)計(jì)算機(jī)技術(shù)與控制工程學(xué)院，黑龍江齊齊哈爾161006)

無線傳感器網(wǎng)絡(luò)（wirelesssensor networks，WSN）是以大量能量有限的智能傳感器為節(jié)點(diǎn)，并將其分布在所要監(jiān)控的區(qū)域內(nèi)，然后對信息進(jìn)行采集、傳輸和處理的一個(gè)網(wǎng)絡(luò)信息系統(tǒng)[1]。拓?fù)淇刂萍夹g(shù)能夠在滿足網(wǎng)絡(luò)連通與覆蓋性基礎(chǔ)上，剔除網(wǎng)絡(luò)中冗余的通信鏈路，提高傳感器節(jié)點(diǎn)數(shù)據(jù)傳輸成功率，保持網(wǎng)絡(luò)能耗均衡，延長網(wǎng)絡(luò)生命時(shí)間及優(yōu)化網(wǎng)絡(luò)性能[2]。

目前，國內(nèi)外學(xué)者對WSN網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄒ呀?jīng)進(jìn)行了相關(guān)研究并取得了一些成果[3]。較為普遍的兩種拓?fù)淇刂品椒楣β士刂芠4]和層次型拓?fù)淇刂芠5]。其中：功率控制主要是以傳感器節(jié)點(diǎn)的功率變化作為切入點(diǎn)，通過在不同時(shí)間段內(nèi)有規(guī)律地控制節(jié)點(diǎn)的功率以達(dá)到降低節(jié)點(diǎn)能耗的目的；層次型拓?fù)淇刂剖且詫鞲衅鞴?jié)點(diǎn)進(jìn)行簇的劃分，以維持網(wǎng)絡(luò)工作的策略。

現(xiàn)有的WSN網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法主要針對網(wǎng)絡(luò)拓?fù)涞倪B通性[6]、能耗均衡[7]、生命周期[8]等方面進(jìn)行優(yōu)化。

在拓?fù)溥B通性方面，Deniz等[9]通過調(diào)節(jié)節(jié)點(diǎn)不同狀態(tài)下的傳輸能力，以確保節(jié)點(diǎn)故障時(shí)網(wǎng)絡(luò)的連通性。Akbari Torkestani[10]在部署網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)為每個(gè)節(jié)點(diǎn)配備具有自我學(xué)習(xí)能力的學(xué)習(xí)機(jī)制，使網(wǎng)絡(luò)具有一定的自適應(yīng)性，極大提高了網(wǎng)絡(luò)的連通。但上述方法對于傳感器節(jié)點(diǎn)的要求過高，造價(jià)過于高昂。郝曉辰等[11]以負(fù)載均衡評價(jià)模型為條件選擇最優(yōu)發(fā)射功率并利用YG圖構(gòu)建拓?fù)浣Y(jié)構(gòu)，該拓?fù)浣Y(jié)構(gòu)雖然降低了網(wǎng)絡(luò)的開銷，但是模型計(jì)算和拓?fù)錁?gòu)建過程較為復(fù)雜。在能耗均衡方面，Wang等[12]提出一種分簇的控制算法，降低了網(wǎng)絡(luò)平均能耗，但其拓?fù)浣Y(jié)構(gòu)的健壯性不強(qiáng)。為了有效提高網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的健壯性，Anderson等[13]利用剛性圖中剛度矩陣能夠?qū)W(wǎng)絡(luò)定位的特性，在定位點(diǎn)選擇過程中，通過提高剛性矩陣特征值的方法來提高網(wǎng)絡(luò)的健壯性。但由于傳感器節(jié)點(diǎn)的能量是有限的，僅考慮網(wǎng)絡(luò)健壯性是不足的，網(wǎng)絡(luò)的生存時(shí)間將是網(wǎng)絡(luò)拓?fù)淇刂频氖滓獑栴}。在網(wǎng)絡(luò)生存周期方面，Zebbane等[14]將網(wǎng)絡(luò)進(jìn)行組劃分，并對傳感器節(jié)點(diǎn)設(shè)置了sleep和wake兩種模式，以此延長傳感器節(jié)點(diǎn)的生存時(shí)間。羅小元等[15]提出了一種基于最小剛性圖代數(shù)特性的拓?fù)鋬?yōu)化算法，該算法綜合考慮了鏈路權(quán)值與剛性圖的剛度問題，使生成的總鏈路權(quán)值較小，網(wǎng)絡(luò)魯棒性較好，延長了網(wǎng)絡(luò)的生存時(shí)間。

傳統(tǒng)的拓?fù)淇刂扑惴ㄊ窃诶硐肭闆r下進(jìn)行的，即節(jié)點(diǎn)是無私的，但在實(shí)際情況中節(jié)點(diǎn)會(huì)自私地降低能耗以保存自身能量。因此，更為合理的一般性假設(shè)為節(jié)點(diǎn)總是自私的，它們之間存在競爭行為，并且可以自主決策[16]。博弈論是具有競爭行為的數(shù)學(xué)理論，對于節(jié)點(diǎn)而言，可以更好地制定節(jié)點(diǎn)間的最佳合理性策略[17]。

Komali等[18]提出一種基于博弈論的分布式拓?fù)淇刂扑惴ǎ∕IA），通過考慮網(wǎng)絡(luò)的連通性和節(jié)點(diǎn)的發(fā)射功率制定了節(jié)點(diǎn)在不同網(wǎng)絡(luò)狀態(tài)下的最佳選擇策略。該算法雖然可以保證網(wǎng)絡(luò)節(jié)點(diǎn)的最大策略選擇，但是在不同的執(zhí)行順序下，網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)是不一樣的。因此Komali在此基礎(chǔ)上進(jìn)行了改進(jìn)，改進(jìn)后的DIA算法[19]保證了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的唯一性。但該算法并未考慮到節(jié)點(diǎn)自身剩余能量問題，在算法的執(zhí)行過程中，雖然降低了網(wǎng)絡(luò)的能耗，但是節(jié)點(diǎn)自身的剩余能量會(huì)加速網(wǎng)絡(luò)節(jié)點(diǎn)能耗的不平衡。李小龍等[20]在構(gòu)建效用函數(shù)時(shí)同時(shí)考慮了網(wǎng)路的連通性和節(jié)點(diǎn)的剩余能量問題，提出了基于勢博弈的分布式拓?fù)淇刂扑惴―EBA，該算法能夠保證網(wǎng)絡(luò)節(jié)點(diǎn)行為存在納什均衡[21]點(diǎn)，且拓?fù)浣Y(jié)構(gòu)具有唯一性，通過網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量有效地均衡了節(jié)點(diǎn)間的能量消耗，延長了網(wǎng)絡(luò)的工作時(shí)間。但該算法沒有考慮到網(wǎng)路中部分節(jié)點(diǎn)在不同狀態(tài)下的節(jié)點(diǎn)度問題，無法保證節(jié)點(diǎn)資源的最優(yōu)設(shè)置。蔡釗等[22]在效用函數(shù)中考慮到了節(jié)點(diǎn)在不同狀態(tài)下的節(jié)點(diǎn)度，規(guī)避了在某單一狀態(tài)下節(jié)點(diǎn)度過大的問題，保證了節(jié)點(diǎn)資源。

上述算法并未考慮到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)的節(jié)點(diǎn)度、網(wǎng)絡(luò)拓?fù)漪敯粜浴㈡溌啡哂嗟葐栴}，能量多的節(jié)點(diǎn)快速耗盡能量而死亡。針對以上問題，作者提出一種基于最優(yōu)剛性子圖的勢博弈無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴āＴ撍惴ㄔ诒ＷC網(wǎng)絡(luò)連通性的條件下，綜合考慮網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量，同時(shí)，對于在網(wǎng)絡(luò)節(jié)點(diǎn)經(jīng)博弈階段均衡能耗后存在的冗余鏈路，提出利用最優(yōu)剛性子圖方法剔除網(wǎng)絡(luò)中的冗余鏈路。

1 模型及相關(guān)理論

1.1 網(wǎng)絡(luò)模型及相關(guān)假設(shè)

1.2 博弈論模型

設(shè)博弈模型為T =〈N,A,U(A)〉，則在博弈中主要包含了個(gè)3個(gè)要素：參與者、策略集、收益函數(shù)。

1）參與者N={1,2,···,n}，其中 n為博弈參與者個(gè)數(shù)。

3）收益函數(shù)U(A)。U={u1,u2,u3,···,ui}，則可用Ui(ai,a-i):A →R表示參與者 i在行為組合(ai,a-i)下的收益。

1.3 剛性圖模型

如圖1所示：在無向圖G=(V,E)中，對于任意兩個(gè)頂點(diǎn)( i,j)∈E， 節(jié)點(diǎn)的運(yùn)動(dòng)軌跡 f(t)滿 足||fi(t)-fj(t)||=d ，其中， d為常數(shù)。若該無向圖中頂點(diǎn)的運(yùn)動(dòng)軌跡是不變的，則稱該無向圖為剛性圖，反之則為可變形圖。

圖1 可變形圖和剛性圖Fig.1 Deformable graph and rigid graph

定義4（最小剛性圖） 如果在維持圖的剛性的情況下，任意地刪除圖中的某一條邊都會(huì)影響該圖的剛性，則稱該圖為最小剛性圖。

定義5（最優(yōu)剛性圖） 如果一個(gè)拓?fù)鋱D是最小剛性圖，并且在相同頂點(diǎn)的條件下圖中鏈路的加權(quán)和最小，那么稱該圖為最優(yōu)剛性圖。

定義6（最優(yōu)剛性子圖） 對于任意的兩個(gè)拓?fù)鋱DG =(V,E)、G′=(V′,E′)，若V′?V ， E′?E 則稱 G′是 G的子圖，當(dāng)且僅當(dāng)圖 G′是最優(yōu)剛性圖時(shí)，稱 G′為 G的最 優(yōu)剛性子圖。

2 網(wǎng)絡(luò)拓?fù)淇刂颇Ｐ?/h2>

2.1 勢博弈模型

WSN拓?fù)淇刂扑惴ㄒC合考慮網(wǎng)絡(luò)連通性、節(jié)點(diǎn)負(fù)載能耗、節(jié)點(diǎn)剩余能量、網(wǎng)絡(luò)生存時(shí)間等多個(gè)目標(biāo)進(jìn)行優(yōu)化。作者利用DEBA算法[11]的效用函數(shù)作為本文勢博弈模型的效用函數(shù)，因此，本文的效用函數(shù)仍然收斂至納什均衡解，對此不做具體證明。效用函數(shù)的具體描述如式（1）所示：

2.2 最優(yōu)剛性子圖矩陣構(gòu)建

1）鏈路權(quán)值構(gòu)建

在無向圖G=(V,E)中，鏈路集E={(i,j)∈V×V:i ≠j}，其中每條鏈路都可以轉(zhuǎn)換為剛性矩陣的行向量。則在2維空間中構(gòu)建剛性矩陣M|e|×2n（ |e|為拓?fù)鋱D中的鏈路總數(shù)）時(shí)，該圖中的第 k 條鏈路 lij在剛性矩陣M 中對應(yīng)的第 k 行元素構(gòu)成的行向量 mk定義為：

3 WSN拓?fù)鋬?yōu)化算法

作者提出了基于最優(yōu)剛性子圖和勢博弈理論相結(jié)合的WSN節(jié)點(diǎn)分布式執(zhí)行網(wǎng)絡(luò)拓?fù)淇刂扑惴?。該算法分為網(wǎng)絡(luò)拓?fù)洳┺呐c拓?fù)浣?、冗余鏈路刪除、拓?fù)渚S護(hù)與修復(fù)3個(gè)階段。具體步驟描述如下：

步驟1：初始化各自的功率為最大功率，初始化傳感器節(jié)點(diǎn)i的最大通信半徑為 rc。節(jié)點(diǎn) i向周圍節(jié)點(diǎn)廣播信息包NCK，NCK={IDi,si,Eri}，其中， IDi為 i標(biāo)志碼， si為 i的位置坐標(biāo)， Eri為i的剩余能量。當(dāng)傳感器節(jié)點(diǎn) j接收到節(jié)點(diǎn)i信息包NCK后，節(jié)點(diǎn) j 向節(jié)點(diǎn)i發(fā)送信息包ACK，ACK={IDj,sj,Erj,pij}，其中， pij為節(jié)點(diǎn) i與節(jié)點(diǎn) j通信所需要的最小功率。當(dāng)節(jié)點(diǎn)i收到周圍節(jié)點(diǎn)j的確認(rèn)信息包ACK后，則節(jié)點(diǎn)i將 節(jié)點(diǎn) j添加至節(jié)點(diǎn)i鄰居信息表中。節(jié)點(diǎn)i通過信息交換后生成策略集P，由式（1）計(jì)算收益實(shí)時(shí)更新信息表，直至達(dá)到均衡解，由最終各節(jié)點(diǎn)的信息表構(gòu)建節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合 R，生成網(wǎng)絡(luò)拓?fù)滏溌穲D。

步驟2：節(jié)點(diǎn)i通過鄰居節(jié)點(diǎn)集合 R計(jì)算鄰居個(gè)數(shù)k，構(gòu)建權(quán)值鏈路集 Wi和子圖矩陣 Gi。由定義4～6判斷自身所構(gòu)建的鏈路集是否滿足構(gòu)建剛性矩陣，若滿足則由式（2）～（5）構(gòu)建剛性矩陣 M，否則重新遍歷下一節(jié)點(diǎn)，且由定義6構(gòu)建最優(yōu)子剛性矩陣 Mc。最終由最優(yōu)剛性子圖矩陣得到待刪除鏈路集合 D，通過 D更新各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合 R。

4 PGOSG算法性能評價(jià)

利用Python設(shè)計(jì)了4組仿真實(shí)驗(yàn)，且給出算法復(fù)雜度分析，以便去驗(yàn)證PGOSG算法的有效性。具體為：實(shí)驗(yàn)1分別從節(jié)點(diǎn)的發(fā)射功率、節(jié)點(diǎn)平均節(jié)點(diǎn)度和鄰居節(jié)點(diǎn)平均剩余能量3個(gè)方面考慮權(quán)重因子 α、β對網(wǎng)絡(luò)拓?fù)湫阅艿挠绊?；?shí)驗(yàn)2對不同算法所構(gòu)建的網(wǎng)絡(luò)拓?fù)滏溌穲D進(jìn)行對比，在不同節(jié)點(diǎn)數(shù)下對比了DEBA、PGOSG這兩種算法的平均節(jié)點(diǎn)度和最大節(jié)點(diǎn)度，分析了PGOSG算法的魯棒性；實(shí)驗(yàn)3在不同節(jié)點(diǎn)數(shù)下對比了DEBA算法和PGOSG算法的平均鏈路長度，分析了PGOSG算法的鏈路質(zhì)量；實(shí)驗(yàn)4在不同節(jié)點(diǎn)下對比了DEBA、PGOSG這兩種算法的最小剩余能量，分析了PGOSG算法的生存時(shí)間。仿真實(shí)驗(yàn)參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)設(shè)置Tab.1 Parameter setting of simulation environment

4.1 算法復(fù)雜度

算法復(fù)雜度是衡量算法計(jì)算量的標(biāo)準(zhǔn)，下面主要分析本文PGOSG算法的時(shí)間復(fù)雜度。PGOSG算法主要包含兩個(gè)階段，即拓?fù)洳┺碾A段和冗余鏈路剔除階段。拓?fù)洳┺碾A段，所有節(jié)點(diǎn)遍歷自身策略由式（1）計(jì)算收益，并由收益確定鄰居集合。博弈階段中，假設(shè)節(jié)點(diǎn)的最大鄰居節(jié)點(diǎn)個(gè)數(shù)為 M（即各節(jié)點(diǎn)的最大策略數(shù)），其中1 ≤M ＜n，則算法復(fù)雜度為 o(M2n)。在冗余鏈路剔除階段，所有節(jié)點(diǎn)需由鄰居集合構(gòu)建剛性圖矩陣，執(zhí)行剛性變換算法，其復(fù)雜度為o(Mn)。綜 上所述，PGOSG算法的復(fù)雜度為 o(M2n)。

4.2 權(quán)重因子對網(wǎng)絡(luò)拓?fù)涞挠绊懛治?/h3>

使在2維監(jiān)測區(qū)域（300 m×300 m）的內(nèi)隨機(jī)放置50個(gè)節(jié)點(diǎn)，經(jīng)過多次實(shí)驗(yàn)后從中截取20組實(shí)驗(yàn)在限定 α 、 β中任意一個(gè)參數(shù)值為1的情況下，調(diào)節(jié)另一參數(shù)以分析算法中權(quán)重因子對網(wǎng)絡(luò)拓?fù)湫阅艿挠绊憽?/p>

由式（1）可知權(quán)重因子 α 、 β存在著某種比例關(guān)系，因此為了便于計(jì)算在限定 α 、 β中任意一個(gè)權(quán)重因子值為1的情況下，調(diào)節(jié)另一權(quán)重因子以分析算法中權(quán)重因子對網(wǎng)絡(luò)拓?fù)湫阅艿挠绊?，以便于選定權(quán)重因子，可得 α 、 β對網(wǎng)絡(luò)性能指標(biāo)影響見圖2、3。

圖2 當(dāng) β=1時(shí) α對網(wǎng)絡(luò)性能指標(biāo)的影響Fig.2 Impact of the value αon the network performance when β=1

圖3 當(dāng)α =1時(shí) β對網(wǎng)絡(luò)性能指標(biāo)的影響Fig.3 Impact of the value βon the network performance when α=1

從圖2中可以看出，節(jié)點(diǎn)的平均發(fā)射功率、平均節(jié)點(diǎn)度、鄰居節(jié)點(diǎn)平均剩余能量隨 α的增大而減小。而圖3中隨著節(jié)點(diǎn)數(shù)目的增大而減少，由此可知權(quán)重因子 α 、 β存在著某種比例關(guān)系。由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一般性理論可知，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的發(fā)射功率較低，同時(shí)又有適中的節(jié)點(diǎn)度，此時(shí)的拓?fù)浣Y(jié)構(gòu)相對完善。因此，由文獻(xiàn)[23]中關(guān)于網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)算能力和網(wǎng)絡(luò)性能指標(biāo)的介紹，作者將 α設(shè) 為1， β設(shè)為1。

4.3 PGOSG魯棒性分析

為對比不同狀態(tài)下的網(wǎng)絡(luò)拓?fù)滏溌穲D結(jié)構(gòu)，在4.2節(jié)相同的仿真環(huán)境中，隨著傳感器節(jié)點(diǎn)數(shù)量從30變化到100時(shí)，比較DEBA算法與作者提出的PGOSG的最大節(jié)點(diǎn)度和節(jié)點(diǎn)平均度，進(jìn)而驗(yàn)證PGOSG算法的網(wǎng)絡(luò)拓?fù)漪敯粜浴?/p>

圖4和5分別為隨機(jī)鏈路圖和最優(yōu)子剛性鏈路圖。從圖4中可以看出，將節(jié)點(diǎn)隨機(jī)置于特定區(qū)域，其所構(gòu)建的鏈路結(jié)構(gòu)圖中存在的鏈路較多，易導(dǎo)致信道間的串?dāng)_和沖突，數(shù)據(jù)包需要多次重傳，從而會(huì)增加節(jié)點(diǎn)的能耗，造成節(jié)點(diǎn)過早死亡。

圖4 隨機(jī)鏈路圖Fig.4 Random link graph

從圖5可以看出，直接使用最優(yōu)剛性子圖方法生成鏈路圖，降低了節(jié)點(diǎn)間的鏈路數(shù)，但并沒有考慮節(jié)點(diǎn)自身的剩余能量和整個(gè)網(wǎng)絡(luò)中能耗的均衡性，網(wǎng)絡(luò)中節(jié)點(diǎn)會(huì)自私的降低自身功率，部分剩余能量較少的節(jié)點(diǎn)也會(huì)參與轉(zhuǎn)發(fā)造成節(jié)點(diǎn)的過早死亡。

圖5 最優(yōu)剛性子圖鏈路圖Fig.5 Link graph of optimal stiffnesssub-graph

圖6、7分別為使用DEBA、PGOSG算法所構(gòu)建的鏈路圖。

圖6 DEBA算法的鏈路圖Fig.6 Link graph of DEBA algorithm

圖7 PGOSG算法的鏈路圖Fig.7 Link graph of PGOSG algorithm

由圖6可見，DEBA算法綜合考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)能耗均衡等問題，使剩余能量多的節(jié)點(diǎn)參與數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，增加的節(jié)點(diǎn)生存時(shí)間。但DEBA算法使剩余能量多的節(jié)點(diǎn)參與過多的冗余轉(zhuǎn)發(fā)，部分節(jié)點(diǎn)所構(gòu)成的子圖中存在著鏈路數(shù)過多，鏈路總權(quán)值較大和網(wǎng)絡(luò)魯棒性較差等問題。由圖7可見，與DEBA算法相比，PGOSG算法在相同參數(shù)環(huán)境下所構(gòu)建的鏈路中的鏈路總數(shù)小于DEBA算法，剔除了網(wǎng)絡(luò)中的冗余鏈路。

圖8、9分別為DEBA和PGOSG算法的節(jié)點(diǎn)的最大度和平均節(jié)點(diǎn)度對比。從圖8、9中可以看出：節(jié)點(diǎn)的最大度隨節(jié)點(diǎn)數(shù)的增加而增加最后趨于穩(wěn)定；節(jié)點(diǎn)的平均節(jié)點(diǎn)度先降低，再隨節(jié)點(diǎn)數(shù)的增加趨于穩(wěn)定。PGOSG算法的最大節(jié)點(diǎn)度低于DEBA算法。在節(jié)點(diǎn)數(shù)增加情況下PGOSG算法的平均節(jié)點(diǎn)度始終小于DEBA算法的且平均節(jié)點(diǎn)度穩(wěn)定在3.5左右，可見網(wǎng)絡(luò)連通情況下PGOSG算法拓?fù)浣Y(jié)構(gòu)相對比較穩(wěn)健。

圖8 DEBA和PGOSG算法的最大節(jié)點(diǎn)度對比Fig.8 Compar ison of the maximum node degr ee by DEBA and PGOSG algorithm

圖9 DEBA和PGOSG算法的平均節(jié)點(diǎn)度對比Fig.9 Comparison of the average node degree by DEBA and PGOSG algorithm

4.4 PGOSG鏈路質(zhì)量分析

在4.2節(jié)相同實(shí)驗(yàn)仿真環(huán)境下，通過改變節(jié)點(diǎn)的個(gè)數(shù)對比分析DEBA和PGOSG算法的平均鏈路長度。

圖10為DEBA算法與作者提出的PGOSG算法隨著節(jié)點(diǎn)數(shù)從30增加到100的網(wǎng)絡(luò)拓?fù)淦骄溌烽L度變化情況。如圖10所示，由DEBA構(gòu)成的拓?fù)浣Y(jié)構(gòu)平均鏈路長度比PGOSG的更長，即節(jié)點(diǎn)數(shù)相同時(shí)DEBA算法因網(wǎng)絡(luò)通信時(shí)網(wǎng)絡(luò)鏈路較長耗費(fèi)更多的資源，而PGOSG算法耗費(fèi)較少，因此PGOSG算法生成的網(wǎng)絡(luò)拓?fù)滏溌焚|(zhì)量較好。

圖10 DEBA和PGOSG算法的平均鏈路長度對比Fig.10 Comparison of the average link length by DEBA and PGOSG algorithm

4.5 PGOSG延長網(wǎng)絡(luò)生存時(shí)間效果分析

4.2節(jié)相同實(shí)驗(yàn)仿真環(huán)境下，在不同節(jié)點(diǎn)數(shù)下對比了DEBA算法和PGOSG算法的網(wǎng)絡(luò)生存時(shí)間。

圖11、12分別為DEBA和PGOSG算法在不同節(jié)點(diǎn)數(shù)下的最小剩余能量和網(wǎng)絡(luò)平局生存時(shí)間對比。

圖11 DEBA和PGOSG算法的最小剩余能量對比Fig.11 Comparison of the minimum residual energy by DEBA and PGOSG algorithm

圖12 DEBA和PGOSG算法的生存時(shí)間對比Fig.12 Comparison of survival time by DEBA and PGOSG algorithm

由圖11可知，DEBA算法雖然關(guān)注了能量的均衡，讓剩余能量多的節(jié)點(diǎn)參與數(shù)據(jù)轉(zhuǎn)發(fā)，但沒有考慮到能量剩余多的節(jié)點(diǎn)在其子圖結(jié)構(gòu)上的鏈路總能耗問題，部分權(quán)值較大的鏈路增加了節(jié)點(diǎn)的負(fù)載。從圖12可以看出：當(dāng)在固定范圍內(nèi)部署節(jié)點(diǎn)密度不同時(shí)，節(jié)點(diǎn)的生存時(shí)間有所差別；當(dāng)區(qū)域內(nèi)節(jié)點(diǎn)密度稀疏或密集時(shí)，網(wǎng)絡(luò)拓?fù)涞逆溌吠ㄐ啪嚯x較長或通信鏈路過多都將導(dǎo)致網(wǎng)絡(luò)拓?fù)渖鏁r(shí)間的不規(guī)則變化；PGOSG算法在固定區(qū)域內(nèi)當(dāng)節(jié)點(diǎn)數(shù)達(dá)到50時(shí)，網(wǎng)絡(luò)拓?fù)涞纳鏁r(shí)間較長，即區(qū)域內(nèi)最佳節(jié)點(diǎn)部署數(shù)。同時(shí)，隨著節(jié)點(diǎn)數(shù)的增加，PGOSG算法的生存時(shí)間總高于DEBA算法，這是因?yàn)镻GOSG算法在均衡節(jié)點(diǎn)能耗的同時(shí)也刪除了部分冗余鏈路，降低了部分節(jié)點(diǎn)的負(fù)載，使得節(jié)點(diǎn)在相同環(huán)境下所造成的能耗較低。

5 結(jié) 論

針對現(xiàn)有勢博弈算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)過多、鏈路總能耗過大、網(wǎng)絡(luò)生存時(shí)間較短、網(wǎng)絡(luò)拓?fù)漪敯粜暂^差等問題，提出了一種基于最優(yōu)剛性子圖和勢博弈的網(wǎng)絡(luò)拓?fù)淇刂扑惴ǎ≒GOSG）。該算法在保證網(wǎng)絡(luò)連通性的基礎(chǔ)下，以勢博弈模型均衡節(jié)點(diǎn)能耗，進(jìn)一步利用了最優(yōu)剛性子圖剔除冗余鏈路。經(jīng)仿真實(shí)驗(yàn)分析了該算法的有效性。下一步研究將針對算法參數(shù)選取的機(jī)械性，采用機(jī)器學(xué)習(xí)實(shí)現(xiàn)自適應(yīng)參數(shù)調(diào)節(jié)機(jī)制。