劉半藤

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

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

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

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

1 粒子模型

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

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

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

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

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

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

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

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

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

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

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

假設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)絡多跳傳輸特性,粒子將承擔轉(zhuǎn)發(fā)任務。因此,粒子將努力向剩余能量較高的鄰居粒子移動,從而降低剩余能量較低的粒子作為中間粒子轉(zhuǎn)發(fā)信息的概率,實現(xiàn)提高網(wǎng)絡生存時間的目的。

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

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

2.3 粒子移動策略

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

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

3 仿真分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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