基于最佳位置點(diǎn)的移動(dòng)代理路由算法

劉 威，葛 斌，張 巖

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

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

1 相關(guān)工作

目前基于Client/Server(C/S)模型的路由算法，存在著節(jié)點(diǎn)能量消耗不均衡和可擴(kuò)展性差等弊端[2-4]。移動(dòng)代理技術(shù)廣泛應(yīng)用于完成無(wú)線傳感器網(wǎng)絡(luò)中感知數(shù)據(jù)收集和處理等任務(wù)[5]。在設(shè)計(jì)移動(dòng)代理模型中，存在的關(guān)鍵問(wèn)題是移動(dòng)代理的路徑遷徙和網(wǎng)絡(luò)結(jié)構(gòu)模型的構(gòu)建。移動(dòng)代理路線設(shè)計(jì)可分為單代理和多代理模式。在設(shè)計(jì)單代理移動(dòng)路線過(guò)程中，移動(dòng)代理從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]，單個(gè)移動(dòng)代理由于要按照一定的次序訪問(wèn)所有的數(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ù)時(shí)延和能耗不均衡等問(wèn)題[8]。在多移動(dòng)代理遷徙路徑規(guī)劃中，將監(jiān)測(cè)區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)分成若干個(gè)分組，把每一個(gè)分組相當(dāng)于一個(gè)單移動(dòng)代理路線規(guī)劃進(jìn)行處理，最后所有的分組內(nèi)移動(dòng)代理將所匯聚數(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算法在為移動(dòng)代理規(guī)劃路徑中主要使用遺傳算法來(lái)實(shí)現(xiàn)，基于GA的算法自適應(yīng)能力差，不能解決傳感器網(wǎng)絡(luò)動(dòng)態(tài)變化的情況，且需要知道全局信息，不適用大規(guī)模網(wǎng)絡(luò)。BST/MST算法通過(guò)考慮總能耗這一主要因素構(gòu)建出最小生成樹(shù)[12]，但未能考慮數(shù)據(jù)源節(jié)點(diǎn)的隨機(jī)分布情況，因此移動(dòng)代理訪問(wèn)數(shù)據(jù)源節(jié)點(diǎn)的數(shù)量波動(dòng)較大，導(dǎo)致產(chǎn)生局部能量開(kāi)銷(xiāo)大和數(shù)據(jù)延遲的情況，影響了網(wǎng)絡(luò)的生存周期。

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

2 問(wèn)題描述

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

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

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

根據(jù)文獻(xiàn)[13]提出的能耗模型，本文重點(diǎn)考慮通信能耗，并假設(shè)忽略其他因素對(duì)能耗的影響。即傳感器節(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所示，移動(dòng)代理位于A、B、C三個(gè)不同的位置，設(shè)SA，SB和SC表示群組中消耗能量最快的區(qū)域，區(qū)域由正六邊形單元組成，EA，EB和EC表示這些區(qū)域消耗的能量。以文獻(xiàn)[14]為基礎(chǔ)，靠近移動(dòng)代理的節(jié)點(diǎn)需要轉(zhuǎn)發(fā)遠(yuǎn)離移動(dòng)代理節(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 移動(dòng)代理位于不同的位置

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

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

當(dāng)移動(dòng)代理移動(dòng)到交叉點(diǎn)C時(shí)，該六邊形單元中的節(jié)點(diǎn)不需要接收數(shù)據(jù)，僅將收集到的數(shù)據(jù)發(fā)送給代理，有6個(gè)六邊形單元可以直接與移動(dòng)代理通信，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)移動(dòng)代理的位置在點(diǎn)A時(shí)，對(duì)于平衡所劃分六邊形能量消耗是最有利的，稱(chēng)點(diǎn)A為最佳位置點(diǎn)。

2.1.3 區(qū)域劃分

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

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

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

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

由以上推導(dǎo)可知，當(dāng)最優(yōu)分簇?cái)?shù)確定后，Stotal可取最小值，此時(shí)網(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ù)（需要對(duì)最優(yōu)分簇?cái)?shù)進(jìn)行取整處理），即可計(jì)算出監(jiān)測(cè)區(qū)域內(nèi)由移動(dòng)代理為簇頭簇的個(gè)數(shù)，在全部覆蓋監(jiān)測(cè)區(qū)域與最大化節(jié)省成本的同時(shí)，兼顧通信時(shí)延，得出最優(yōu)分簇?cái)?shù)。

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

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

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

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

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

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

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

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

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

3.2 算法研究

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

3.2.1 粒子速度和位置更新

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

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

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

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

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

當(dāng)S3k＞0時(shí)，說(shuō)明粒子群找到了更優(yōu)秀的解；當(dāng)S3k=0時(shí)，算法可能找到了全局最優(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)重較小時(shí)，算法擁有良好的局部搜索能力。當(dāng)學(xué)習(xí)因子較大時(shí)，粒子群尋優(yōu)力度較大，需要降低慣性權(quán)重，反之需要增大慣性權(quán)重。因此，對(duì)慣性權(quán)重系數(shù)實(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次時(shí)粒子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)對(duì)粒子歷史最優(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個(gè)粒子，對(duì)于粒子向量表示為速度為迭代最大次數(shù)為kmax。計(jì)算粒子的BA值、EI值、局部最優(yōu)值及全局最優(yōu)值；

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

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

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

步驟5:對(duì)迭代次數(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算法，主要通過(guò)總能量消耗、任務(wù)延遲、移動(dòng)代理路徑均衡度三個(gè)方面對(duì)比這四類(lèi)算法的性能。

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

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

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

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

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

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

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

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

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

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

5 小結(jié)

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