王 茜，崔志華，王麗芳

(太原科技大學 計算機科學與技術學院，太原 030024)

1 引 言

目前，由傳感器、微處理器和無線通信接口組成的傳感器網絡已經應用在醫(yī)療[1]、農業(yè)[2]和工業(yè)[3]等眾多領域.由電池[4]供電的傳感器通常分布在作戰(zhàn)區(qū)這樣的危險區(qū)域，傳感器節(jié)點不僅承擔著監(jiān)測數據的任務，還需要接收、處理和發(fā)送數據等一系列工作.經過一定周期的工作后，傳感器消耗了大量的能量，需要及時補充能量.所以，傳感器的能量問題成為研究的熱點.解決節(jié)點的能量問題分為3大類：低功耗路由協議[5，6]、能量收集[7]和無線充電[8].低功耗路由協議的設計，雖然可以降低節(jié)點的能耗，但隨著時間的推移，節(jié)點會因為能量耗盡而停止工作，從而影響無線傳感網絡的正常工作.另外可以通過能量收集的方式補充能量，然而從環(huán)境中獲取的能量是很難預測的，而且很不穩(wěn)定.例如，在獲取太陽能的過程中通常會受到天氣的影響，這對于傳感器的正常運行來說是低效的.無線充電則是第3種新穎的技術，就是將無線充電技術和移動充電設備引入到傳感器網絡中，形成無線可充電傳感器網絡(WRSNs)[9].由于傳感器節(jié)點在網絡區(qū)域內分布較為廣泛，需要使用能夠充電的設備移動到節(jié)點處進行能量的補充.在大多數場景中，通常利用攜帶大容量電池的移動充電車輛為傳感器補充能量.在移動和充電的過程中，面臨的充電問題和設計的充電方案隨之產生.

根據不同的充電需求，充電場景的設計也是不同的.在小規(guī)模傳感器網絡中，對于為數不多的充電請求，設計一個充電小車即可滿足需求.但對于大規(guī)模傳感器網絡來說，由于充電小車的自身能量有限，一個充電小車短時間內不足以響應大量的充電請求，此時需要設計多個充電小車的網絡.為了及時為傳感器節(jié)點補充能量，解決傳感器網絡的經典能量問題，研究人員設計了多樣化的可充電傳感器網絡，并且關于充電小車的研究正在不斷深入根據充電小車的個數，可分為單充電小車的充電設計和多充電小車的充電設計.為了有效利用無線充電技術來延長網絡壽命，Peng等人[10]設計了基于一個充電小車的無線可充電傳感器網絡系統(tǒng)，通過一個能量站來實時監(jiān)測傳感器節(jié)點的能量狀態(tài)，確定充電小車的充電順序.并且，建立了該系統(tǒng)的概念原型，通過實驗驗證了實際系統(tǒng)的可行性，該系統(tǒng)的設計對于實際可充電傳感器網絡具有重要意義.除了對系統(tǒng)的設計和理論的驗證，更多地是對充電設計的優(yōu)化，即充電小車的路徑優(yōu)化求解、充電小車的部署等優(yōu)化問題.Shi等人[11]研究了以充電小車休息時間最大化為目標的優(yōu)化問題，同時證明了充電小車的最優(yōu)路徑是最短的哈密頓循環(huán).同樣是最大化充電小車的休息時間，Wang等人[12]側重于充電路徑規(guī)劃的合理性做了進一步研究，根據已部署傳感器網絡的初始拓撲結構，將無線傳感器網絡劃分為多個子網絡.綜合分析不同傳感器節(jié)點的能量狀態(tài)和位置，將整個網絡的優(yōu)化充電路徑問題轉化為子網絡的局部優(yōu)化問題，求解出每個子網絡中動態(tài)網絡拓撲下的最優(yōu)充電路徑，以此延長傳感器網絡的壽命.

與此同時，研究人員也考慮到了對多輛充電小車的充電設計.多輛充電小車單獨負責小部分傳感器節(jié)點的充電，共同維持整個網絡的生命周期.在多充電小車的傳感器網絡中，面臨的重要問題是充電成本，最小化充電小車數量和最大化充電效率是眾多研究的優(yōu)化目標.Wang等人[13]主要研究了多充電小車調度問題，在網絡中心設置了一個中心調度器，當收到充電請求時，將立即分配充電小車進行充電.并且，規(guī)劃了均勻和局部兩種充電請求，對兩種充電策略(分配最近充電小車去充電和分配距離較遠充電小車去充電)進行了評估.為了盡可能地提高能量利用率，在不考慮移動充電小車自身能量的條件下，Zhang等人[14]提出了一種新型的協同移動充電模式，各個移動充電小車之間可以相互傳輸能量，以此來擴大充電范圍.而Liu等人[15]首先最小化充電小車數量，在確定最小數量之后再對路徑長度最小化，最后達到低能耗的目的.此外，Chen等人[16]提出對充電小車的速度參數進行優(yōu)化，創(chuàng)造了移動過程中的充電機會，對以往先移動后充電的方法進行了創(chuàng)新，減少了最終的充電完成時間.

此外，充電優(yōu)化問題的算法求解工作也有著一些突破，通過最短路徑算法及一些不同的啟發(fā)式算法來求解最優(yōu)路徑，可以使得移動充電小車的能量利用率提高，同時極大降低了充電成本和時間.俞立春等人[17]將精英策略引入到蛙跳算法[18]中，使用該算法求解出一條使小車能量利用率最大化的最優(yōu)路徑.陳花等人[19]考慮到小車自身能量有限，設計了周期性充電規(guī)劃策略，在最大化充電周期的同時最小化充電小車能量消耗，以延長網絡的生命周期，利用混沌粒子群算法[20]求解最優(yōu)的充電路徑和合理的充電時間.魏振春等人[21]則以最大化能量利用率和最小化數據傳輸時延為目標建立了聯合充電和數據收集的多目標路徑規(guī)劃模型，通過多目標蟻群算法[22]求得了該多目標問題的Pareto最優(yōu)解集.針對節(jié)點位置固定、能耗消耗快而導致的網絡生命周期短的問題，夏靜山等人[23]提出了一種考慮路徑長度和能耗的雙重目標下的充電路徑優(yōu)化方法，并使用遺傳算法[24]來求解最優(yōu)充電路徑.但在實際充電問題中，如果充電小車僅在一個節(jié)點位置上耗費太多的充電時間，那么其他急需充電的節(jié)點將等待較長的時間，這樣的充電過程對于延長網絡生命周期是低效的.所以，不僅要考慮小車自身的能量消耗，還需對充電時間進行規(guī)劃，當充電小車大于一輛時，充電小車的數量也不可忽視.

本文的主要工作有以下幾點：首先建立了具有多輛多種充電小車的可充電傳感器網絡場景，綜合考慮充電小車行駛總路徑、充電總時間和小車分配成本作為成本目標；同時，對原本的鴿群算法作出了改進，提出基于自適應慣性權重的速度更新公式.然后將改進的鴿群算法和遺傳算法進行混合，用新的混合算法對充電路徑規(guī)劃問題求解；最后利用Matlab仿真工具進行了實驗驗證，以此證明設計的算法解決實際問題的有效性.

2 多輛多種充電小車的模型與問題描述

2.1 網絡模型

考慮一種多充電小車的可充電傳感器網絡作為本研究的網絡模型，圖1為設計的網絡模型.傳感器的工作主要是監(jiān)測、處理和發(fā)送數據等，在監(jiān)測區(qū)域內，隨機部署了大量傳感器節(jié)點和基站，節(jié)點之間通過多跳路由將監(jiān)測的數據發(fā)送給基站.多個移動充電小車從基站出發(fā)，遍歷每個待充電的節(jié)點集，依次為待充電節(jié)點進行無線充電，最后，所有的充電小車返回到基站休息來補充能量.在圖1中，空心節(jié)點為急需充電的節(jié)點，三角形表示為基站，長方形表示為充電小車，黑色線段為充電小車充電路徑，箭頭指向下一個需要充電的節(jié)點.

圖1 網絡模型

2.2 問題描述

在傳感器網絡中，傳感器的工作主要是對監(jiān)測數據的處理.在數據傳輸過程中，節(jié)點會消耗自身的能量，能量消耗模型如下所示.當節(jié)點能量達到最低值時，需要及時進行能量補充.

接收K比特數據時消耗的能量為：

Er=ERX*CM

(1)

在這里，ERX表示為接收每比特信息消耗的能量，數值為50×10-13J/b，CM表示為接收數據中控制信息的大小，數值為32bit.

傳輸K比特數據時消耗的能量為：

(2)

在這里，ETX表示為傳輸每比特信息消耗的能量，數值為50×10-13J/b；DM表示為傳輸數據中數據信息的大小，數值為4000bit；Efs表示為節(jié)點自身耗散的能量，數值為10×10-13J/b；d表示每個節(jié)點到基站的距離；由于距離基站較遠的節(jié)點，消耗的能量更多.所以用d0表示節(jié)點到基站之間的距離臨界值，其值為30m.

在本文中，設置一定數目的兩種不同電池容量的充電小車，以此來補充節(jié)點的能量消耗.在這個過程中，主要研究的問題是：成本最小化的多車充電路徑規(guī)劃.即，在成本最小化的目標下，合理分配出最小數量的充電小車，并且每個小車所能承受的充電能力沒有超過自身的電池容量.將該問題形象描述為：

minF

(3)

約束條件如下：

max(N)≤N

(4)

er(Ci)≤ec0，1≤i≤N

(5)

(6)

ec(Vm)≤e0，1≤m≤M

(7)

rm≤tm≤dm

(8)

公式(4)表示充電小車的分配數量N不超過充電小車的總數，公式(5)表示第i個充電小車補充給傳感器節(jié)點的能量er不超過小車自身能量，公式(6)表示需要補充能量的節(jié)點數量不超過整個節(jié)點序列V，公式(7)表示第m個節(jié)點消耗的能量不超過節(jié)點自身的能量(能量約束).公式(8)表示時間約束，充電小車給第m個節(jié)點充電的時間tm在申請充電請求時刻rm和最后維持時刻dm之間(時間約束).

(9)

(10)

f3=N1·cost1+N2·cost2，0≤N1+N2≤N

(11)

F：argmin{f1，f2，f3}

(12)

成本理論上由可變成本和固定成本兩部分組成，在充電過程中，路徑距離和充電總時間是一個可變成本，它們會因為待充電的節(jié)點不同而變化，而車輛自身包含固定成本，每個車型都有不同的成本系數，由表1可知，當分配車輛數目不確定

表1 參數設置

時，車輛成本也隨之變化.關于成本最小化由公式(12)所示，綜合考慮了路徑距離、充電時間和車輛成本3個目標.公式(9)為路徑距離，是每個充電小車為對應的節(jié)點序列進行充電的距離總和.公式(10)為充電時間，充電小車為節(jié)點充電的時間應該在公式(8)的約束范圍內，當充電小車到達節(jié)點的時間大于維持能量的最后時間時，將產生節(jié)點等待的時間成本ncost；當充電小車提前到達節(jié)點時，將產生充電小車等待的時間成本ccost.公式(11)為充電小車的車輛成本，兩種充電小車的電池容量不同，則兩種車輛的成本系數cost也不同，并且分配車輛的數目N不超過充電小車總數.

3 改進的鴿群算法和遺傳算法的混合UPIOGA

3.1 PIOGA混合算法的基本思想

鴿群算法是近年來才出現的一種群體智能優(yōu)化算法，它是受自然界中鴿群自主歸巢行為的啟發(fā)而提出的.鴿群具有良好的導航和記憶能力，這對尋優(yōu)過程非常有利.但在基本的鴿群算法中容易陷入局部極值，降低算法準確性，并且收斂速度不穩(wěn)定.遺傳算法則屬于模擬演化規(guī)律的算法之一，通過設定初始的種群，然后以迭代的方式對種群進行選擇、交叉、變異操作，最終得到適應性更強的種群，具有全局收斂性.本文通過將遺傳算法與鴿群算法結合來解決路徑規(guī)劃問題，首先使用遺傳算法大范圍內搜索一組粗略解，然后以這組粗略解作為鴿群算法的初始種群，最后利用鴿群算法的指南針等特性進一步搜尋鄰近區(qū)域可能的解.該混合算法既具有遺傳算法全局尋優(yōu)的特性，又具備鴿群算法的鄰域尋優(yōu)特性，從整體上提高了算法的執(zhí)行效率.具體算法步驟：

1)初始化n個網絡節(jié)點坐標，產生初始的遺傳算法種群；

2)將每一條充電路徑作為種群中的每個個體，計算每個個體的適應值，本文中的適應值函數f由公式(12)和(13)共同得出；

3)通過遺傳算法中的選擇、交叉和變異操作，以此更新種群；

4)達到預定的迭代次數后，輸出初步優(yōu)化后的種群；

5)由4)得到的種群作為鴿群算法的初始種群，進一步鄰域尋優(yōu)；

6)初始化鴿群算法中的參數，參數值如表1所示；

7)計算每只鴿子的適應值，同(2)；

8)地圖和指南針算子更新，利用公式(15)和公式(16)更新個體的位置和速度，循環(huán)迭代要求的次數(在表1設定)后得到當前最好的位置；

9)將8)的個體位置移交給地標算子，繼續(xù)按照要求的迭代次數循環(huán)更新，在每次循環(huán)中將鴿子的總數折半，對當前位置按照適應值函數排序，排在后半段的鴿子被認為遠離目的地并且不熟悉地標，從而被舍棄；

10)迭代結束后，輸出最終優(yōu)化后的種群.完整的算法流程圖如圖2所示.

圖2 算法流程圖

3.2 混合算法PIOGA中的遺傳操作

3.2.1 編碼

對于充電車輛路徑規(guī)劃問題，本文采用自然數編碼原則.假設m輛車為n個傳感器節(jié)點進行充電服務，染色體編碼為(0，i11i12，…，i1a，0，i21i22，…，i2b，0，…，0，im1，…，imn，0)，其中0代表傳感器網絡中的基站，即所有充電小車的起始位置，a，b，…，n指的是每個小車負責充電的節(jié)點個數，它們負責充電的節(jié)點個數是隨機無序的，同時a，b，…，n這些數量不超過傳感器節(jié)點數量n.1，2，…，m指的是m輛小車的編號，而兩個0之間的序列表示每一個充電小車行走的子路徑.通過算法優(yōu)化，最終可以求解出最佳路徑，并從路徑中可以得出充電車輛的分配數量.

3.2.2 適應值函數和選擇操作

多車輛的充電路線優(yōu)化問題的優(yōu)化目標就是要找到充電成本最小的車輛路線.因此，本文將3個目標f1，f2，f3線性整合為一個單目標F，F由公式(12)得到，1/F作為該算法的適應值函數f.

(13)

選擇操作采用輪盤賭法，選擇生命力強的個體繁殖后代產生新的種群.假設N為種群數目，fi為某個個體i的適應值，則該個體被選擇的概率為：

(14)

3.2.3 交叉

交叉是進化算法中的重要過程，通過交叉，子代才能繼承父代的優(yōu)良性狀.在本文中，采用如下交叉方式：

假設兩條父代的染色體編碼為p1和p2，其中：

1)隨機初始化交叉點的位置和交叉長度.

2)分別找出p1和p2的交叉段，將p1的交叉段插入p2的交叉點中，將p2的交叉段插入p1的交叉點中，交叉成為s1和s2.

3)刪除s1和s2中重復的編碼，得到新的s1和s2.交叉實例圖如圖3所示.

圖3 交叉實例圖

3.2.4 變異

變異操作是為了增加種群的多樣性，是指按照一定的概率將染色體中的某些基因轉變成其他基因的過程.變異概率一般在5%以下.采用如下變異操作：

設染色體的編碼長度為L.

1)隨機生成兩個不等的正整數r1和r2，且r1，r2均小于等于L.

2)交換染色體中的第r1位和第r2位基因.如圖4所示.

圖4 變異實例圖

3.3 鴿群算法的改進

在復雜環(huán)境下采用鴿群算法進行路徑規(guī)劃時，存在容易陷入局部最優(yōu)、收斂速度較慢和不穩(wěn)定等問題，所以在本文中對鴿群算法進行了改進，引入自適應權重系數對種群中個體的速度、位置進行計算，由公式(15)、公式(16)所示，以提高鴿群算法的執(zhí)行效率和滿足最優(yōu)路徑規(guī)劃.

(15)

(16)

(17)

其中，Vi和Xi表示第i個個體第t次迭代后的速度和位置，w為慣性權重，rand為隨機數，Xg為當前迭代的全局最優(yōu)值.在公式(17)中通過適應值函數f的比較來對慣性權重進行取值，f為公式(13)所提到的成本適應值函數，f與當前鴿群的平均成本值進行比較.

4 仿真實驗及結果分析

4.1 場景和參數設置

為了驗證算法和模型的有效性，設置了兩種實驗場景：傳感器節(jié)點隨機均勻分布在網絡區(qū)域內和傳感器節(jié)點呈圓環(huán)分布在網絡區(qū)域內，如圖5(a)、圖5(b)所示.對于整個充電過程中涉及到的參數，取值如表1所示.本實驗環(huán)境采用MatalbR2016a版本對UPIOGA算法進行仿真.采用對比法，與PIO算法、GA算法、基本的PIOGA混合算法和經典的HSGA混合算法分別在同一場景下進行比較.

4.2 實驗結果

由圖5(c)、圖5(d)、圖5(e)可以得出，兩種節(jié)點分布相比較而言，均勻分布更適合本文的算法和模型，在圓環(huán)分布下的成本過高，節(jié)點位置固定，不具有隨機性.通過大量的仿真實驗，可以驗證5種不同算法下的充電性能.表2列出了基于5種算法的充電成本和路線，并且對充電車輛分配情況做出了說明.從表2中可以得出，改進的PIOGA算法(UPIOGA)下的充電成本最小，充電路線更佳.與此同時，在圖6基于5種算法的路線軌跡圖中，UPIOGA算法的充電分布更均衡，提高了每個充電小車的能量利用率.

表2 充電成本和路線

圖5 節(jié)點分布比較

圖6 基于5種算法的對比結果

從表3測試問題的計算結果來看，UPIOGA算法的評價指標，即算法均值、最好值、均方差均好于算法GA、PIO的評價指標，雖然GA的最差值較好，但其均方差比UPIOGA算法較大.同時，從圖6(f)的收斂曲線來看，UPIOGA算法既克服了單一算法過早收斂的不足，也獲取了更好的解，能較好地保持算法的全局優(yōu)化性能.

表3 5種算法對充電車輛問題的仿真實驗結果

5 結 論

本文針對多充電小車路徑規(guī)劃問題，對基本的成本目標模型進行了改進：路徑距離、充電時間和車輛成本綜合考慮為一個充電成本目標.同時，對基本的鴿群算法進行了改進：在原有的個體速度公式基礎上，增加關于實際充電成本的自適應慣性權重.最后將改進的鴿群算法與遺傳算法混合為一個新的算法UPIOGA，基于UPIOGA算法求解充電路徑問題.仿真實驗證明了模型的合理性和算法的有效性.

在未來的工作中，可以將充電效率、能量消耗和充電車輛數量等因素綜合考慮，使充電路徑問題成為一個高維多目標優(yōu)化問題.