劉 威，葛 斌，張 巖

(1.安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001；2.阜陽師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，安徽 阜陽 236037)

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)憑借自組織、低成本、長生存周期的特點(diǎn)，而廣泛應(yīng)用于地質(zhì)勘測、醫(yī)療護(hù)理等領(lǐng)域。但是由于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量受限且不可補(bǔ)充，使WSN的能量資源有限，無法長時間滿足感知數(shù)據(jù)的收集和處理。因此如何有效利用網(wǎng)絡(luò)的能量資源是WSN中最具挑戰(zhàn)性的問題之一[1]。

1 相關(guān)工作

目前基于Client/Server(C/S)模型的路由算法，存在著節(jié)點(diǎn)能量消耗不均衡和可擴(kuò)展性差等弊端[2-4]。移動代理技術(shù)廣泛應(yīng)用于完成無線傳感器網(wǎng)絡(luò)中感知數(shù)據(jù)收集和處理等任務(wù)[5]。在設(shè)計(jì)移動代理模型中，存在的關(guān)鍵問題是移動代理的路徑遷徙和網(wǎng)絡(luò)結(jié)構(gòu)模型的構(gòu)建。移動代理路線設(shè)計(jì)可分為單代理和多代理模式。在設(shè)計(jì)單代理移動路線過程中，移動代理從Sink結(jié)點(diǎn)出發(fā)完成數(shù)據(jù)匯聚任務(wù)后返回Sink節(jié)點(diǎn)。例如局部最近鄰優(yōu)先(local closest first，LCF)[6]和全局最近鄰優(yōu)先(global closest first，GCF)[7]，單個移動代理由于要按照一定的次序訪問所有的數(shù)據(jù)源節(jié)點(diǎn)，在小規(guī)模網(wǎng)絡(luò)中能有效的節(jié)約能耗，但是不適用于大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)或復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，存在著數(shù)據(jù)時延和能耗不均衡等問題[8]。在多移動代理遷徙路徑規(guī)劃中，將監(jiān)測區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)分成若干個分組，把每一個分組相當(dāng)于一個單移動代理路線規(guī)劃進(jìn)行處理，最后所有的分組內(nèi)移動代理將所匯聚數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。例如GA-MIP（genetic algorithm based multi agent itinerary planning)[9]算法、DSG-MIP(directional source grouping based multi agent itinerary planning)[10]算法、BST(balancing MST-MIP Algorithm)/MST(minimum spanning tree based multi agent itinerary planning)[11]算法等。GA-MIP算法在為移動代理規(guī)劃路徑中主要使用遺傳算法來實(shí)現(xiàn)，基于GA的算法自適應(yīng)能力差，不能解決傳感器網(wǎng)絡(luò)動態(tài)變化的情況，且需要知道全局信息，不適用大規(guī)模網(wǎng)絡(luò)。BST/MST算法通過考慮總能耗這一主要因素構(gòu)建出最小生成樹[12]，但未能考慮數(shù)據(jù)源節(jié)點(diǎn)的隨機(jī)分布情況，因此移動代理訪問數(shù)據(jù)源節(jié)點(diǎn)的數(shù)量波動較大，導(dǎo)致產(chǎn)生局部能量開銷大和數(shù)據(jù)延遲的情況，影響了網(wǎng)絡(luò)的生存周期。

針對局部移動代理負(fù)載不均衡問題，本文首先將網(wǎng)絡(luò)區(qū)域進(jìn)行六邊形劃分，選取出移動代理收集數(shù)據(jù)的最佳位置點(diǎn)(best point,LP)，以移動代理的負(fù)載均衡和總能耗為優(yōu)化目標(biāo)，提出基于改進(jìn)粒子群的移動代理路由算法(MABOPSO)，把移動代理訪問LP點(diǎn)的順序看做粒子，經(jīng)過迭代更新，為移動代理尋找最優(yōu)路徑。

2 問題描述

2.1 MA路徑規(guī)劃問題

假設(shè)無線傳感器網(wǎng)絡(luò)由N個同構(gòu)傳感器節(jié)點(diǎn)組成，網(wǎng)絡(luò)中存在一個固定的Sink結(jié)點(diǎn)，在監(jiān)測區(qū)域內(nèi)所產(chǎn)生的數(shù)據(jù)信息通過M個移動代理的移動傳遞至Sink節(jié)點(diǎn)。移動代理規(guī)劃目標(biāo)是最小化移動代理負(fù)載的均衡度從而尋找出最優(yōu)路徑。

2.1.1 網(wǎng)絡(luò)能耗模型

根據(jù)文獻(xiàn)[13]提出的能耗模型，本文重點(diǎn)考慮通信能耗，并假設(shè)忽略其他因素對能耗的影響。即傳感器節(jié)點(diǎn)的通信能耗ETotal：

其中：ETx(k,d)與ERx(k)分別為節(jié)點(diǎn)發(fā)送、接收kb數(shù)據(jù)的所消耗的能耗；εelec為發(fā)送1 b數(shù)據(jù)所需要的能耗；εfs為比例系數(shù)；d為矢量距離。

2.1.2 最佳位置點(diǎn)

如圖1所示，移動代理位于A、B、C三個不同的位置，設(shè)SA，SB和SC表示群組中消耗能量最快的區(qū)域，區(qū)域由正六邊形單元組成，EA，EB和EC表示這些區(qū)域消耗的能量。以文獻(xiàn)[14]為基礎(chǔ)，靠近移動代理的節(jié)點(diǎn)需要轉(zhuǎn)發(fā)遠(yuǎn)離移動代理節(jié)點(diǎn)的數(shù)據(jù)而承擔(dān)更多的任務(wù)，這些區(qū)域的總數(shù)據(jù)量表示為∑D(u)，∑D(v)和∑D(w)，ρ為節(jié)點(diǎn)分布密度，E0為節(jié)點(diǎn)初始能量，Se為六邊形的面積，μ為能量節(jié)省率。

圖1 移動代理位于不同的位置

移動代理處于3個六邊形單元的交叉點(diǎn)時，傳感器節(jié)點(diǎn)不需要接收數(shù)據(jù)并且僅需要向移動代理發(fā)送傳感數(shù)據(jù)。有9個六邊形單元可以與移動代理通信，A點(diǎn)的能量節(jié)省率為：

移動到交叉點(diǎn)時，B在2個六邊形單元中的節(jié)點(diǎn)不需要接收數(shù)據(jù)，B點(diǎn)的能量節(jié)省率為：

當(dāng)移動代理移動到交叉點(diǎn)C時，該六邊形單元中的節(jié)點(diǎn)不需要接收數(shù)據(jù)，僅將收集到的數(shù)據(jù)發(fā)送給代理，有6個六邊形單元可以直接與移動代理通信，C點(diǎn)的能量節(jié)省率為：

其中：u為六邊形單元Ci中的節(jié)點(diǎn)；Ds(u)為節(jié)點(diǎn)u收集到的數(shù)據(jù)量；DR(u)為節(jié)點(diǎn)u轉(zhuǎn)發(fā)的數(shù)據(jù)量?？傻忙藺＞μB＞μC，因此，當(dāng)移動代理的位置在點(diǎn)A時，對于平衡所劃分六邊形能量消耗是最有利的，稱點(diǎn)A為最佳位置點(diǎn)。

2.1.3 區(qū)域劃分

為了確定移動代理收集數(shù)據(jù)的LP，找尋出最利于均衡網(wǎng)絡(luò)能耗的移動代理路徑，在保證劃分的正六邊形能夠全部覆蓋監(jiān)測區(qū)域的情況下，將網(wǎng)絡(luò)監(jiān)測區(qū)域進(jìn)行劃分，基站計(jì)算出正六邊形的邊長L，結(jié)合能耗、網(wǎng)絡(luò)時延和成本等因素，計(jì)算出移動代理收集數(shù)據(jù)的群組?？梢杂?jì)算出最佳位置點(diǎn)數(shù)目與正六邊形個數(shù)相同，根據(jù)文獻(xiàn)[15]對最優(yōu)六邊形數(shù)目Mopt推導(dǎo)。

其中：EPL、Enon-PL分別表示移動代理在最佳位置點(diǎn)收集數(shù)據(jù)所消耗的能量和傳感器節(jié)點(diǎn)與移動代理通信所消耗的能量；M表示正六邊形個數(shù)；εDA表示融合數(shù)據(jù)所消耗的能量；DtoMA表示節(jié)點(diǎn)到移動代理的距離對ETotal求M的一階導(dǎo)數(shù)并令其為0，可得最優(yōu)分簇?cái)?shù)Mopt。

式（7）最優(yōu)分簇?cái)?shù)只考慮了分簇?cái)?shù)對能耗的影響，沒有涉及時延。為此，對分簇?cái)?shù)進(jìn)行改進(jìn)。設(shè)新的性能指標(biāo)參數(shù)為Stotol，推導(dǎo)出最優(yōu)分簇?cái)?shù)。

其中:Ttatal表示移動代理在簇內(nèi)收集數(shù)據(jù)所花費(fèi)的時間和通信時延的總和；α為能耗和時間的權(quán)重因子；β為時間和成本的權(quán)重因子；Ctotal表示移動代理的成本。根據(jù)對以上ETotal的推導(dǎo)，可以得出分簇?cái)?shù)Mopt與Stotal的關(guān)系

由以上推導(dǎo)可知，當(dāng)最優(yōu)分簇?cái)?shù)確定后，Stotal可取最小值，此時網(wǎng)絡(luò)性能指標(biāo)達(dá)到最優(yōu)。由于式（7）計(jì)算出的分簇?cái)?shù)是簇內(nèi)單跳通信最優(yōu)分簇?cái)?shù)，現(xiàn)在將這種簇表示為六邊形單元，而式（10）中得到的新最優(yōu)分簇?cái)?shù)（需要對最優(yōu)分簇?cái)?shù)進(jìn)行取整處理），即可計(jì)算出監(jiān)測區(qū)域內(nèi)由移動代理為簇頭簇的個數(shù)，在全部覆蓋監(jiān)測區(qū)域與最大化節(jié)省成本的同時，兼顧通信時延，得出最優(yōu)分簇?cái)?shù)。

2.2 優(yōu)化粒子群模型的構(gòu)造

粒子群算法(particleswarm optimization，PSO)是源于鳥群覓食行為活動的智能算法[16-18]，粒子通過學(xué)習(xí)全局最優(yōu)解和局部最優(yōu)解而改變其運(yùn)動速度和位置，經(jīng)過若干次的學(xué)習(xí)最終得到最優(yōu)解。但由于傳統(tǒng)的PSO不能有效的解決離散的優(yōu)化問題[19]，本文運(yùn)用MABOPSO算法解決移動代理路徑規(guī)劃問題，其模型簡單且能快速收斂。MABOPSO算法使用粒子歷史最優(yōu)解、局部最優(yōu)解和全局最優(yōu)解更新其位置和速度，使粒子群具有多樣性特點(diǎn)的同時有效地避免早熟現(xiàn)象的出現(xiàn)。

為了均衡移動代理訪問群組內(nèi)所有數(shù)據(jù)源節(jié)點(diǎn)的能耗，本文進(jìn)行以下均衡度定義：

其中：Ei為節(jié)點(diǎn)i的剩余能量；Eave為所有節(jié)點(diǎn)的平均剩余能量；Lj為單移動代理j的長度；Lave為所有移動代理的平均長度。均衡度為BA=Eba+λLba，Eba和Lba衡量粒子群在無線傳感器網(wǎng)絡(luò)中性能評價標(biāo)準(zhǔn)，λ為能耗和路徑的比例系數(shù)，λ=1，依次表示為群組內(nèi)能量分部程度和群組內(nèi)移動代理路徑遷徙長度。值越小說明均衡度越好[20]。

因此，基于優(yōu)化粒子群的移動代理路徑規(guī)劃問題可以轉(zhuǎn)化為以下離散多目標(biāo)問題

其中：Tu表示移動代理收集數(shù)據(jù)消耗時間；T0表示允許的最大傳輸時延。

3 算法實(shí)現(xiàn)

3.1 粒子群優(yōu)化模型

本文設(shè)計(jì)優(yōu)化粒子群算法MABOPSO，把移動代理訪問最佳位置（LP）的不同順序看做每一個粒子，迭代更新若干輪，以總能耗、移動代理的負(fù)載均衡和最大允許的訪問時間為目標(biāo)，對新的移動代理路徑進(jìn)行評價，尋找最優(yōu)路徑。

3.2 算法研究

第k次迭代后所有粒子值的平均值為：

3.2.1 粒子速度和位置更新

粒子的自學(xué)習(xí)更新速度受粒子群局部最優(yōu)值和全局最優(yōu)值的影響，為了便于研究單個粒子的尋優(yōu)能力和整個粒子群的尋優(yōu)能力。定義粒子第k次迭代的尋優(yōu)度為：

Slk反映粒子i在經(jīng)過k次迭代后的尋優(yōu)能力參數(shù)。Slk＞0時，說明粒子i尋找到更優(yōu)秀的解；S1k=0時，說明粒子i可能處于停滯的狀態(tài)。

第k次迭代粒子群局部最優(yōu)尋優(yōu)度為：

當(dāng)S2k＞0時，說明粒子找到了更優(yōu)秀的解；當(dāng)S2k=0時，說明粒子i可能找到局部最優(yōu)解或處于停滯的狀態(tài)。

定義第k次迭代的粒子群全局最優(yōu)平均值的尋優(yōu)度為：

當(dāng)S3k＞0時，說明粒子群找到了更優(yōu)秀的解；當(dāng)S3k=0時，算法可能找到了全局最優(yōu)值或者趨于停滯。定義第k次迭代的學(xué)習(xí)因子公式為：

其中，α,β,γ∈[0,1]，且α+β+λ=1。由于學(xué)習(xí)因子的目標(biāo)在于尋找出全局最優(yōu)解，所以λ＞ max(α,β)。

尋優(yōu)因子是判斷當(dāng)前粒子平均值與全局最優(yōu)值接近程度的參數(shù)，則第k次迭代的尋優(yōu)因子為：

在粒子群速度公式中，慣性權(quán)重影響算法的搜索能力。若慣性權(quán)重比較大，則算法擁有強(qiáng)大的全局搜索能力；若慣性權(quán)重較小時，算法擁有良好的局部搜索能力。當(dāng)學(xué)習(xí)因子較大時，粒子群尋優(yōu)力度較大，需要降低慣性權(quán)重，反之需要增大慣性權(quán)重。因此，對慣性權(quán)重系數(shù)實(shí)時調(diào)整

其中：w為初始慣性權(quán)重；a和b為調(diào)節(jié)學(xué)習(xí)E0和pk的系數(shù)，0＜a,b＜1，且a+b=1。所以第k+1次時粒子i第d維的改進(jìn)速度為：

第k+1次粒子i第d維位置為:

3.2.3 更新最優(yōu)解

適應(yīng)度函數(shù)以網(wǎng)絡(luò)負(fù)載均衡BA和總能耗EI為目標(biāo)。結(jié)合適應(yīng)度函數(shù)值判斷當(dāng)前的粒子的狀態(tài)，采用公式(22)對粒子歷史最優(yōu)解進(jìn)行更新，設(shè)置迭代更新最優(yōu)解的次數(shù)n，每一輪更新后判斷粒子是否滿足成為歷史最優(yōu)解的條件，若n次迭代后粒子歷史最優(yōu)解仍未更新，則產(chǎn)生新的粒子。粒子全局最優(yōu)解取決于粒子歷史最優(yōu)解的更新。設(shè)定閾值θ，如果 | pbesti-gbest|＜θ，則pbesti加入全局最優(yōu)解集合，否則刪除粒子。

3.3 算法實(shí)施

步驟1：初始化n個粒子，對于粒子向量表示為速度為迭代最大次數(shù)為kmax。計(jì)算粒子的BA值、EI值、局部最優(yōu)值及全局最優(yōu)值；

步驟2：初始化迭代次數(shù)k=1；

步驟3：根據(jù)公式(23)更新粒子i的位置

步驟4：對粒子i函數(shù)值進(jìn)行更新，并更新出局部最優(yōu)函數(shù)值和全局最優(yōu)函數(shù)值，并計(jì)算出下一輪的改進(jìn)權(quán)重系數(shù)，對下一輪粒子的迭代速度進(jìn)行更新；

步驟5:對迭代次數(shù)進(jìn)行判斷，判斷是否等于kmax，若不等于，則k=k+1，返回步驟3，若等于kmax，則輸出全局最優(yōu)函數(shù)值集合，結(jié)束算法。

4 仿真實(shí)驗(yàn)與結(jié)果分析

為證明本文所提出的基于優(yōu)化粒子群算法MABOPSO的有效性，選取LCF算法、GCF算法和GA-MIP算法，主要通過總能量消耗、任務(wù)延遲、移動代理路徑均衡度三個方面對比這四類算法的性能。

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文使用Matlab R2016a平臺做仿真實(shí)驗(yàn)，實(shí)驗(yàn)參數(shù)見表1。

表1 仿真實(shí)驗(yàn)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果分析

數(shù)據(jù)源節(jié)點(diǎn)數(shù)，設(shè)置為5～40，仿真中設(shè)置100個隨機(jī)數(shù)種子，在總能量消耗方面(取平均值)對四類算法進(jìn)行比較，如圖2。當(dāng)數(shù)據(jù)源節(jié)點(diǎn)數(shù)較少時，MABOPSO算法、LCF算法、GCF算法和GAMIP算法在總能量消耗方面大致相同，隨著數(shù)據(jù)源節(jié)點(diǎn)數(shù)的增加，LCF算法明顯存在著優(yōu)勢，由于多移動代理算法需要多個移動代理協(xié)作完成感知數(shù)據(jù)的匯聚，每個移動代理在進(jìn)行數(shù)據(jù)匯聚時增加了額外的能耗開銷。在路徑選擇中充分考慮了移動代理負(fù)載均衡，因此總能耗低于同類算法。

圖2 數(shù)據(jù)源節(jié)點(diǎn)數(shù)對總能量消耗的影響

圖3為數(shù)據(jù)源節(jié)點(diǎn)數(shù)量與任務(wù)延遲之間的關(guān)系，隨著訪問數(shù)據(jù)源節(jié)點(diǎn)數(shù)目的增加，數(shù)據(jù)延遲整體將呈現(xiàn)上升的趨勢。LCF算法在任務(wù)延遲方面性能遠(yuǎn)低于多移動代理算法，單移動代理隨著數(shù)據(jù)源節(jié)點(diǎn)數(shù)增加而出現(xiàn)較大延遲，而多個MA以協(xié)作的方式同時訪問分布在網(wǎng)絡(luò)區(qū)域的數(shù)據(jù)源節(jié)點(diǎn)，將會有效的降低任務(wù)延遲。因?yàn)閱蝹€代理訪問節(jié)點(diǎn)增加，所以GA-MIP、GCF任務(wù)延遲有所增加。而MABOPSO算法由于是在網(wǎng)絡(luò)區(qū)域劃分后選取最佳位置點(diǎn)的基礎(chǔ)上進(jìn)行移動代理路徑規(guī)劃，因此能有效的減小延遲。

圖3 數(shù)據(jù)源節(jié)點(diǎn)數(shù)對任務(wù)延遲的影響

移動代理均衡度有效衡量了移動代理路徑規(guī)劃算法的性能，圖4中LCF算法均衡度明顯低于其他3種算法，而 GA-MIP、GCF和MABOPSO算法在數(shù)據(jù)源節(jié)點(diǎn)較少時性能相似，隨數(shù)據(jù)源節(jié)點(diǎn)數(shù)的增加，MABOPSO算法的均衡度優(yōu)于GAMIP、GCF，充分說明MABOPSO算法的有效性。

圖4 數(shù)據(jù)源節(jié)點(diǎn)數(shù)對移動代理均衡度的影響

5 小結(jié)

本文通過對網(wǎng)絡(luò)通信區(qū)域的劃分，引入最佳位置點(diǎn)讓移動代理匯聚數(shù)據(jù)更加高效，并以粒子群算法為基礎(chǔ)對其進(jìn)行優(yōu)化，結(jié)合學(xué)習(xí)因子和尋優(yōu)因子改進(jìn)速度公式的權(quán)重因子，計(jì)算每一個粒子的BA值和能耗EI，迭代更新找出移動代理的最優(yōu)移動路線。在不同數(shù)據(jù)源節(jié)點(diǎn)的條件下，依次與LCG、GCF和GA-MIP算法進(jìn)行總能量消耗、任務(wù)延遲和移動代理均衡度等方面的比較。實(shí)驗(yàn)結(jié)果表明本算法在考慮移動代理負(fù)載均衡的無線傳感器網(wǎng)絡(luò)中能夠有效優(yōu)化移動代理路徑且有效減少網(wǎng)絡(luò)能耗，相比于同類算法更好的實(shí)現(xiàn)了負(fù)載均衡，從而延長網(wǎng)絡(luò)生存周期。