基于能量粒子算法的無線自組織網(wǎng)絡(luò)節(jié)點移動策略研究*

劉半藤

(浙江樹人大學(xué)信息工程學(xué)院,杭州 310015)

無線自組織網(wǎng)絡(luò)MANETs(Mobile Ad Hoc Networks)是由若干可以自由移動節(jié)點組成的高度自治系統(tǒng)。由于部署MANETs無需依靠已有的通信設(shè)備,具有較強(qiáng)的抗毀性與適用性,被廣泛地應(yīng)用于抗震救災(zāi)、野外探測等各種環(huán)境,被視為21世紀(jì)信息技術(shù)的重要產(chǎn)業(yè)支柱之一[1]。受限的節(jié)點能量與動態(tài)變化的拓?fù)浣Y(jié)構(gòu)是MANETs區(qū)別于傳統(tǒng)網(wǎng)絡(luò)的重要特征。由于MANETs節(jié)點大多分布于野外環(huán)境中,需要依靠電池供電且長時間內(nèi)無法充電。網(wǎng)絡(luò)能耗已經(jīng)成為限制MANETs發(fā)展的重要因素,也成為國內(nèi)外專家學(xué)者研究的熱點領(lǐng)域[2]。節(jié)點的移動使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)實時變化,網(wǎng)絡(luò)能量優(yōu)化計算變得更為困難。因此,研究一種節(jié)點移動策略改善網(wǎng)絡(luò)能耗狀況是一項非常有意義的工作。

目前,MANETs節(jié)點移動策略對于網(wǎng)絡(luò)性能的影響主要表現(xiàn)在以下幾個方面[3-10]:時間同步問題、網(wǎng)絡(luò)連通性問題、網(wǎng)絡(luò)能耗問題、網(wǎng)絡(luò)覆蓋率問題。王慧強(qiáng)等人[3]針對水下傳感器網(wǎng)絡(luò)移動性對時間同步參數(shù)計算帶來的困難,提出一種通信量小、精度高的時間同步算法。劉宴濤等人[4]分別建立隨機(jī)點移動策略、隨機(jī)方向移動策略、隨機(jī)游走移動策略分析MANETs連通性狀況,證明隨機(jī)游走移動策略使得網(wǎng)絡(luò)具有較高連通性。與此同時,王珊珊等人[5]改進(jìn)傳統(tǒng)的隨機(jī)游走移動策略,并在仿真平臺NS3實現(xiàn)一種以圓形為邊界的隨機(jī)游走移動模型,以提高網(wǎng)絡(luò)連通性。吳聰?shù)热薣6]在經(jīng)典隨機(jī)點移動策略基礎(chǔ)上,建立能量均衡的線性規(guī)劃數(shù)學(xué)模型,說明節(jié)點移動性有助于提升MANETs能耗均衡性。無獨有偶,Pala等人[7]利用節(jié)點移動特性,建立線性規(guī)劃模型對無線傳感網(wǎng)絡(luò)的能量均衡指標(biāo)進(jìn)行優(yōu)化。王珊等人[8]建立節(jié)點移動模型,提出一種修復(fù)網(wǎng)絡(luò)覆蓋空洞的聯(lián)合補(bǔ)丁法,從而實現(xiàn)降低網(wǎng)絡(luò)節(jié)點冗余度和提高網(wǎng)絡(luò)覆蓋率的目的。Wang等人[9]針對無線傳感網(wǎng)絡(luò)覆蓋問題,指出在網(wǎng)絡(luò)中部署少量移動節(jié)點有助于提高網(wǎng)絡(luò)覆蓋性能,并在三種典型應(yīng)用場景進(jìn)行仿真分析。Liu等人[10]從二維平面入手,考慮一般凸三維曲面的覆蓋率,并以此作為傳感器節(jié)點移動特征參數(shù),及時填補(bǔ)覆蓋空洞。在上述幾方面中,節(jié)點移動對于網(wǎng)絡(luò)覆蓋性與能耗均衡兩方面的研究更加重要。如何通過節(jié)點移動性,提升網(wǎng)絡(luò)整體覆蓋性以及改善能耗指標(biāo)是衡量移動策略的重要指標(biāo)。由于網(wǎng)絡(luò)節(jié)點移動性使得網(wǎng)絡(luò)能耗優(yōu)化模型計算變得更為復(fù)雜。目前,MANETs節(jié)點移動策略主要有以下幾種方式:虛擬力算法VFA(Virtual Force Algorithm)、粒子群算法PSO(Particle Swarm Optimization)。李明等人[11]結(jié)合傳統(tǒng)虛擬力算法和差分算法,提出一種異構(gòu)無線傳感網(wǎng)絡(luò)的節(jié)點移動策略,提升網(wǎng)絡(luò)覆蓋性能,且計算效率較高。李娟等人[12]以路由算法為基礎(chǔ),建立包含障礙物模型、速度初始化函數(shù)、無邊界仿真區(qū)域的粒子群算法,并進(jìn)行數(shù)值仿真以此說明算法的有效性。傳統(tǒng)的粒子群算法在計算迭代過程中每個粒子都要實時獲得全局最優(yōu)的粒子位置,利用全局最優(yōu)位置和局部最優(yōu)位置信息指導(dǎo)粒子移動。這一點在MANET節(jié)點移動過程中較難實現(xiàn)。如果MANETs節(jié)點實時獲知網(wǎng)絡(luò)所有粒子的位置,需要進(jìn)行集中式控制,所花費代價也較大。因此,較多傳統(tǒng)的粒子群算法較難直接應(yīng)用于MANETs。

為此,本文提出一種基于能量粒子的節(jié)點移動策略EPSO(Energy Particle Swarm Optimization)。EPSO將網(wǎng)絡(luò)中的節(jié)點類比為粒子,每個節(jié)點都可以獲得本地節(jié)點能量的局部最優(yōu)信息和鄰居節(jié)點的局部最優(yōu)信息。通過將鄰居節(jié)點的局部最優(yōu)信息看作全局較優(yōu)解,從而制定策略指導(dǎo)節(jié)點進(jìn)行移動,提升網(wǎng)絡(luò)能耗性能。

1 粒子模型

1.1 網(wǎng)絡(luò)連通率計算方法

由N個移動節(jié)點構(gòu)成的MANET可視為N個粒子散布在網(wǎng)絡(luò)中(下文將網(wǎng)絡(luò)中的節(jié)點稱為粒子),并對粒子進(jìn)行標(biāo)號為i=1,2,…,N。在時刻t,標(biāo)號為i的粒子位置可以表示為向量Pi(t)={pxi(t),pyi(t)}。每個粒子都具備相同的通信半徑Rcom和感知半徑Rcov。粒子可以與通信半徑內(nèi)的其他粒子進(jìn)行信息交互。在時刻t,MANET連通矩陣C(t)=(cij(t))N×N的計算方式如下所示:

如果cij(t)=1,說明該時刻兩個粒子間的距離小于通信半徑。此時,該兩個粒子可以直接進(jìn)行信息交互。由于MANET的多跳傳輸特性,在連通矩陣C(t)的基礎(chǔ)上,經(jīng)過多跳傳輸后粒子間連通狀況矩陣MC(t)=[mcij(t)]N×N的計算方式如下所示:

如果mcij(t)=1,說明該時刻兩個粒子可以通過多跳傳輸進(jìn)行信息交互。在時刻t,網(wǎng)絡(luò)連通率指標(biāo)L(t)的計算方式如下所示:

該指標(biāo)衡量可以統(tǒng)計某時刻可以實現(xiàn)兩兩信息交互的粒子對總數(shù)所占網(wǎng)絡(luò)粒子對總數(shù)的百分比。一種較好的移動策略可以有效保障粒子之間的連通特性。

1.2 網(wǎng)絡(luò)覆蓋率計算方法

將原有的MANET進(jìn)行網(wǎng)格化劃分,離散成M個獨立的特征點,并對這些特征點進(jìn)行標(biāo)號為i=1,2,…,M。標(biāo)號為i的特征點位置可以表示為向量Pti(t)={xi(t),yi(t)}。在時刻t,粒子對于特征點的覆蓋狀況矩陣G(t)=[gij(t)]N×M的計算方式如下所示:

如果gij(t)=1,說明該時刻標(biāo)號為i的粒子可以感知標(biāo)號為j的特征點。對于某個特征點而言,若存在一個粒子可以感知該特征點則可認(rèn)為該特征點被覆蓋。定義網(wǎng)絡(luò)粒子i的冗余度yi(t)為該節(jié)點感知范圍內(nèi)的特征點被覆蓋的平均粒子數(shù),計算方式如下:

對于某個特征點而言,若存在一個粒子可以感知該特征點則可認(rèn)為該特征點被覆蓋。在時刻t,特征點被覆蓋的狀況矩陣TG(t)=[tgj(t)]1×M的計算方式如下所示:

利用特征點被感知的數(shù)量占特征點總數(shù)近似計算網(wǎng)絡(luò)覆蓋率F(t)計算方式如下:

1.3 網(wǎng)絡(luò)能耗計算方法

假設(shè)MANET粒子能量消耗方式服從一階能耗模型[13],結(jié)構(gòu)如圖1所示。

圖1 一階能量消耗模型

粒子發(fā)送數(shù)據(jù)包消耗能量包括發(fā)射電路耗能、放大電路耗能兩部分,粒子接收數(shù)據(jù)只有接收電路消耗能量,計算方式如下:

式中:ETx表示發(fā)送能量消耗,ERx表示接收能量消耗,Eelec表示發(fā)射電路和接收電路的能耗,l表示發(fā)送數(shù)據(jù)包的比特數(shù),d表示發(fā)送粒子與目的粒子之間的傳輸距離,εfs是模型常數(shù)。

2 能量粒子移動策略

2.1 粒子能量維全局較優(yōu)解與局部最優(yōu)解計算方法

圖2 粒子能量維局部最優(yōu)解與全局較優(yōu)解搜索圖

圖3 粒子能量信息搜索舉例

由于MANET網(wǎng)絡(luò)多跳傳輸特性,粒子將承擔(dān)轉(zhuǎn)發(fā)任務(wù)。因此,粒子將努力向剩余能量較高的鄰居粒子移動,從而降低剩余能量較低的粒子作為中間粒子轉(zhuǎn)發(fā)信息的概率,實現(xiàn)提高網(wǎng)絡(luò)生存時間的目的。

2.2 粒子覆蓋維全局較優(yōu)解與局部最優(yōu)解計算方法

圖4 粒子覆蓋維局部最優(yōu)解與全局較優(yōu)解搜索圖

2.3 粒子移動策略

通過上式可以發(fā)現(xiàn):t時刻第i個節(jié)點根據(jù)自身的位置坐標(biāo)Pi(t)確定需要改變的移動速度fi(t+Δt),從而確定下一時刻的節(jié)點位置Pi(t+Δt)。其中,c1與c2被稱為學(xué)習(xí)因子或者加速度常數(shù);r1與r2是屬于[0,1]范圍內(nèi)服從均勻分布的隨機(jī)數(shù);ω被稱為慣性權(quán)重。

這就是本文提出的能量粒子移動策略EPSO,改善傳統(tǒng)PSO算法所要求的全局最優(yōu)粒子位置無法獲得的困境。本文僅考慮從能量角度對經(jīng)典的PSO算法進(jìn)行改進(jìn),如果要考慮多個因素時也可構(gòu)建多維PSO算法求解節(jié)點移動多目標(biāo)優(yōu)化解。因此,本文的算法具有較好的擴(kuò)展性。

3 仿真分析

為了驗證該能量粒子移動策略的性能,本節(jié)采用MATLAB2018b構(gòu)建一個300 m×300 m矩形MANET仿真環(huán)境。初始時刻,網(wǎng)絡(luò)中隨機(jī)散布著50個移動節(jié)點,每個節(jié)點的覆蓋半徑為50 m,通信半徑為60 m。節(jié)點進(jìn)行業(yè)務(wù)傳輸時首先選擇剩余能量較高的節(jié)點作為中間節(jié)點轉(zhuǎn)發(fā)信息。

假設(shè)網(wǎng)絡(luò)初始時刻每個節(jié)點的初始能量為10 J。設(shè)移動策略參數(shù)為c1=c2=2,ω=1。對比僅用局部最優(yōu)信息的粒子群移動策略(PSO)和傳統(tǒng)的虛擬力移動策略(VFA),三種移動策略下網(wǎng)絡(luò)覆蓋率指標(biāo)變化曲線如圖5所示,三種移動策略下網(wǎng)絡(luò)連通率指標(biāo)變化曲線如圖6所示。

圖5 三種策略下網(wǎng)絡(luò)覆蓋率指標(biāo)變化趨勢圖

圖6 三種策略下網(wǎng)絡(luò)連通率指標(biāo)變化趨勢圖

通過圖5、圖6可以發(fā)現(xiàn):網(wǎng)絡(luò)節(jié)點的移動特性可以有效地提高網(wǎng)絡(luò)覆蓋率指標(biāo),且本文提出的EPSO策略覆蓋率高于僅用局部最優(yōu)信息的PSO策略和傳統(tǒng)的虛擬力移動策略(VFA)。但是,三種移動策略均使得網(wǎng)絡(luò)連通性指標(biāo)提交較為緩慢。這是由于在移動過程中對于連通度指標(biāo)考慮不足所造成。

定義MANET中剩余能量最低的節(jié)點為瓶頸節(jié)點。三種移動策略下網(wǎng)絡(luò)瓶頸節(jié)點能量變化曲線如圖7所示,三種移動策略下網(wǎng)絡(luò)剩余節(jié)點數(shù)量如圖8所示。

圖7 三種策略網(wǎng)絡(luò)瓶頸節(jié)點能量變化趨勢圖

圖8 三種策略網(wǎng)絡(luò)生存節(jié)點數(shù)變化趨勢圖

通過圖7、圖8可以發(fā)現(xiàn):EPSO移動策略下,網(wǎng)絡(luò)的瓶頸節(jié)點隨時間發(fā)生著變化,且瓶頸節(jié)點的能量隨時間下降的速度較僅考慮局部信息的粒子群算法移動策略與傳統(tǒng)虛擬力移動策略更為緩慢,可以延長網(wǎng)絡(luò)生存時間。

4 結(jié)束語

本文在分析網(wǎng)絡(luò)節(jié)點能量消耗模型的基礎(chǔ)上,借鑒粒子群的移動方式,提出了一種能量粒子群算法的無線自組織網(wǎng)絡(luò)節(jié)點移動策略。EPSO將網(wǎng)絡(luò)中的節(jié)點類比為粒子,每個節(jié)點都可以獲得本地節(jié)點能量的局部最優(yōu)信息和鄰居節(jié)點的局部最優(yōu)信息。通過將鄰居節(jié)點的局部最優(yōu)信息看作全局較優(yōu)解,從而制定策略指導(dǎo)節(jié)點進(jìn)行移動,提升網(wǎng)絡(luò)能耗性能。