一種移動充電器對無線傳感器節點充電的調度模型?

神顯豪郭 泰牛少華張烈平

(1.桂林理工大學廣西嵌入式技術與智能系統重點實驗室，廣西 桂林 541004；2.北京理工大學機電學院，北京 100081)

傳統無線傳感器網絡(Wireless Sensor Network，WSN)的壽命常常被節點(Sensor Nodes，SNs)的能量瓶頸所制約[1]。盡管許多研究人員在節能方面做出了很大的努力，有限的能量仍然是WSN長期運行的瓶頸[2]。為了延長SNs的有效壽命，現有的研究主要考慮使用無線能量傳輸的方法對無線傳感器節點進行能量補充[3]。無線能量傳輸的主要思想是利用電磁效應或磁諧振耦合對SNs進行充電。基于無線能量傳輸的充電方案主要分為兩類，即周期性充電方案[4]和按需充電方案[5]。Hu等人[6]研究了基于多充電器的周期性充電時間規劃和充電路徑規劃問題。Dai[7]等人針對移動充電器在大規模無線傳感器網絡中不能有效的工作的問題，提出了一種周期性充電的近似算法。Lyu等人[8]提出了一種基于有限移動能量的周期性充電方案，這種方案根據節點能量的周期性變化對節點進行充電。由于節點的能耗具有很大的不確定性，因此這種方案并不適合具有動態變化的大規模可充電無線傳感器網絡。按需充電方案是只有當節點的能量水平低于給定閾值發出充電請求，基站接收到請求后安排無線充電車(Wireless Charging Vehicle，WCV)對節點充電。Lyes Khelladi[9]提出了一種基于分組請求的按需充電模式。Dong[10]提出了一種通過節點位置、剩余能量、歷史貢獻來選擇按需充電節點的方案。Jiang[11]提出了一種新穎地根據節點充電請求自由移動充電裝置的充電方案。

現有方案主要是通過考慮節點的能量因素來制定服務計劃，它們都有效地延長了網絡壽命。然而在充電過程中節點的時間與空間因素也至關重要，因此這些方案都具有一定的局限性。綜合考慮節點在充電過程中的時間和空間因素，同時考慮節點的能量消耗，設計了一種針對WCV調度的按需充電方案。以充電過程中所產生的延遲作為評價指標，采用線性規劃構建了針對移動充電器的調度問題模型，以節點的時間和空間約束推導適應度函數，使用改進的引力搜索算法來制定具體的服務計劃。最終，WCV按照服務計劃攜帶多個低成本的可分離式充電裝置在多位置對節點并發服務。

1 系統模型

1.1 無線傳感器網絡模型

假設無線傳感器網絡模型由一組隨機部署的可充電傳感器節點組成，基站位于網絡中心，用于接收和處理數據。WCV攜帶多個低成本的可分離式充電裝置在區域中行駛，按照服務計劃為請求節點放置或回收充電裝置，WCV僅執行放置或回收動作，執行完畢即繼續行駛，以實現對節點的多位置并發充電。每個可分離式充電裝置攜帶一定的能量，其中一個可分離式充電裝置一次只能為一個節點充電，在充電完成時向基站發送回收請求，之后被過路的WCV所回收。每次放置充電裝置前，WCV對裝置剩余能量和充電請求隊列中下一個待充電節點的剩余能量進行比對判斷，如果此裝置所攜帶的電能足夠為下一個請求節點充電，則將其放置在下一個請求節點旁，否則隨行駛的WCV最終回到基站補充能量。假設每個SNs規格相同，部署后呈現靜止狀態，兩個節點間的距離稱為歐式距離。節點在傳輸數據和接收數據時所消耗的能量是不同的，因此，節點在某一段時間內的能耗也是不同的[12]。當每個節點的能量低于給定閾值時，節點向基站發送一個服務請求，基站接收到服務請求后，將制定好的服務計劃連同節點地理位置一起發送給相應WCV，WCV從基站出發，按照計劃依次為節點服務。本文采用與文獻[13]相近的WSN網絡模型，該模型用數學公式表達如下:

式中:Ps為充電裝置傳輸能量的發射功率，Cr為節點接收能量的功率，dist(si，w)表示節點si到WCV的歐式距離，Gx為發射模塊增益，Gy，為接收模塊增益，Lp為極化損耗，ε為信號波長，ω為整流器效率，β為弗里斯傳輸方程中的可調參數。

1.2 多約束線性規劃的無線充電車調度模型

在上述WSN網絡模型中，WCV負責補充節點能量，每個節點都配備一個規格相同的電池。但是每個節點的能耗卻不同，例如距離基站較近的節點需要負責承擔中繼任務，傳輸的數據比距離基站較遠的節點多，能耗也遠遠高于位于遠處的節點。因此，聯合考慮節點的能量水平和地理位置來調度WCV為節點服務成為了一項至關重要的工作。本文兼顧時間和空間因素，采用線性規劃的方法定義本文中所要解決的問題。下面定義兩個布爾變量如下:

式中:當rij＝1時，代表節點si在第j輪向基站發送充電請求，其他情況時rij＝0。當cij＝1時，代表節點si在第j輪正在被充電，其他情況則視為cij＝0。

設Nt為傳感器網絡運行時間，cdelay為充電延遲，同時將處理過后的服務請求順序定義為cschedule，即服務計劃表。則上述問題可以用線性規劃定義為:

目標:最小化cdelay

約束條件如式(4):

式中:?i:1≤i≤N，N為節點總數，cradius為充電半徑。

約束(4)(a)表示在任意一輪充電中，充電計劃的數量必須等于向基站發送充電請求的節點數量。約束(4)(b)表示在某一輪充電中，一個充電裝置只能為一個節點充電。約束(4)(c)表示節點必須位于充電半徑以內才可充電。

2 基于改進引力搜索算法的節點服務規劃算法

2.1 經典引力搜索算法

引力搜索算法(Gravity Search Algorithm，GSA)是一種基于現代種群算法的隨機優化算法，它來源于物理學中的萬有引力定律[14]。根據萬有引力定律，每個質點總是向質量更大的質點靠近。假設在d維空間中，算法進行到第t次迭代時，質點xi對質點xj的引力定義如下:

式中:G(t)為引力常量，質點xi的被動引力質量用Wpi(t)表示，質點xj的主動引力質量用Wαj(t)表示，xi與xj之間的歐式距離表示為Rij(t)，φ是一個微小常量。第一次迭代時的初始引力常數為G0，γ為控制參數的值，最大次數迭代表示為tmax。在GSA中，質點xi在t時刻，受到d維上的總力可以定義如下:

式中:n為隊列中服務請求總數因此在迭代時，m為質點總數，xi的加速度可以表示為:

Wii(t)為質點xi在第t次迭代中的慣性質量。質點xi的速度和位置由式(7)決定。

式中:有randj∈[0，1]。質點xi的質量Wi則由式(10)的適應度函數所決定。

式中:第t次迭代時質點xi的適應度用fiti(t)表示，在m個質點中最好情況和最壞情況的適應度值分別用best(t)和worst(t)表示，best(t)和worst(t)定義如下:

2.2 適應度函數的構建

眾所周知，線性規劃是將多目標問題組合為單目標問題，組合后的單目標問題具有易于理解、計算的優點。然而在線性規劃方法中指標的定性與定量相結合，又會產生主觀性過強的問題，從而在一定程度上影響評價結果的準確性。GSA作為一種智能優化算法，在解決單目標優化問題上具有獨特的優勢。在經典GSA當中，問題的解決方案由質點所代表，質點的質量代表著解決方案的性能，質量越大代表著方案性能越好。因此，每個質點可以代表在請求服務隊列當中一個完整的服務計劃，則這些計劃可以表示為:

式中:x i表示服務請求隊列中的第i個請求，n為請求總數，xw i表示xi是在充電請求隊列中第w個充電請求。首先初始化每個參數，即1≤i≤N，N為傳感器網絡中節點總數，1≤w≤n，n為隊列中服務請求總數。初始服務計劃由請求隊列中每個請求的質點xi作升序排序得到。在得到初始服務計劃后，需要構建適應度函數來對每個在服務請求隊列中的質點xi進行評估。定義以下幾個參數來構建適應度函數。

①旅行時間:WCV從當前位置移動到待充電節點所用的時間，表示為Ttime(W→Si):

式中:v為WCV在此過程中運行速度。

②充電時間:在對節點充電過程中所花費的時間，表示為Ctime(W→Si):

式中:ei為節點Si的初始能量，remainSi為節點的剩余能量。

除上述兩個參數，WCV為節點裝卸充電裝置所花費的時間也是充電延遲的一部分。然而，在實際服務過程中，裝卸充電裝置所花費的時間是固定的，且遠小于WCV的旅行時間以及節點的充電時間，因此不會對算法的結果產生影響。本文將充電延遲定義為WCV處理服務請求計劃當中每個請求所花費的平均時間，表示為cdelay:

式中:?Si∈Cschedule。

當WSN中的充電延遲降低時，被充電的節點會顯著增加，則WSN工作壽命也會隨之增加，因此選擇充電延遲作為適應度函數，即:

2.3 基于改進引力搜索算法的節點服務規劃算法

在經典GSA的執行過程當中，所有質點都在向質量最大的那部分質點靠攏，由于算法的迭代次數和搜索空間成反比，隨著迭代次數的增加，搜索空間必然減小，算法運行的最終結果很有可能變成局部最優解。為避免算法陷入局部最優解，維持勘探與開發能力的平衡，更好地提升算法性能，提出了一種基于混沌優化機制的自適應改進方案。混沌優化機制具有非線性、遍歷性和發散性的特點，可以勝任全局優化任務，與隨機變量優化機制相比，混沌優化機制通常表現出更好的搜索行為[15]。本文提出了一種混沌模型，它可以使用單峰映射來選出Kbest。單峰映射是一種由簡單非線性方程產生混沌現象的經典范例，Kbest表示一組K個最佳質點，且只有Kbest當中的質點會對其他質點產生作用力。該模型定義如下:

式中:z(t)∈[0，1]是第t次迭代的混沌數。初始值z0在區間[0，1]被隨機初始化，μ是一個正常數，根據Ji等人[16]的研究，取μ＝4作為最佳值。根據所提出的混沌模型，針對Kbest的混沌優化模型表達如下:

式中:tmax表示最大迭代次數，N為質點總數(即傳感器節點總數)，finalper表示對其他質點產生作用力的質點占質點總數的百分比。在迭代初始狀態中，所有質點均對其他質點產生作用力，finalper的值為1。隨著迭代的進行，搜索空間逐漸變小，finalper的值逐漸趨于穩定，此時算法就有逐漸陷入局部最優解的趨勢。由于每次迭代結果都與上一次的迭代結果有關，因此混沌模型的加入又會直接影響finalper的值，且混沌模型在迭代過程中呈現發散趨勢，因此混沌優化機制的加入可以良好地幫助算法擺脫局部最優解。

在每次迭代產生Kbest后，為了維持勘探和開發能力的平衡，加快收斂速度，本文在混沌優化基礎上將算法作自適應優化。定義Kbest當中的質點為“重質點”，其他質點為“輕質點”。受物理學當中向心力和離心力的啟發，重質點對其他質點既可以產生引力，也可以產生斥力。每個重質點都有一個假設半徑，該半徑隨算法的迭代次數而變化，定義為式(19):

式中:t為當前迭代次數。對于每個重質點，以其當前位置(定義如式(9))為圓心，R為半徑作一圓形區域。在該區域內，重質點對其他輕質點產生引力，根據式(5)和式(6)，重質點對其他輕質點產生的引力定義為式(20):

式中:G(t)為引力常量，質點xi的被動引力質量為Wpi(t)，質點xj的主動引力質量為Wαj(t)，xi與xj之間的歐式距離為Rij(t)，φ是一個微小常量。rn ij表示在n維中xi與xj之間的距離，定義為式(21):

同樣地，若輕質點在上述圓形區域外，則重質點對輕質點產生斥力，根據式(9)，斥力可以定義為:

算法運行時，首先初始化一個變量gfit，以存儲目前為止找到的最優服務計劃的適應度函數值。同樣地，初始化一個變量gbest用于存儲這些充電計劃的位置向量。在不滿足終止條件前，反復更新G(t)、best(t)、worst(t)、Kbest的質量，質點的速度、加速度和位置。定義rqueue為發送請求的ID數組，round為所有SNs將數據傳輸到基站一次所需要的時間。通常，充電延遲越小的質點性能越好，因此其質量也就越大。具體算法實現如算法1所示。

算法1 基于改進GSA的服務計劃生成算法

算法1所生成的cschedule是一個針對所有節點的最佳服務計劃，然而節點的能耗變化往往是一個實時動態的過程，因此，有必要實時為節點更新服務計劃，以最大化延長網絡壽命。通過考慮節點的實時能耗與WCV的當前距離來確定WCV下一步的服務計劃。請求服務的順序不僅會影響到當前需要服務的節點，還會對未服務的節點造成一定影響。同時，能量消耗率也間接地代表著服務需求的頻率，例如當前有一個能量消耗率較低的節點接近WCV，同時又有一個能量消耗率較高的節點距離WCV較遠，這時WCV就需要作出一個合理的選擇。如果僅考慮距離因素，很有可能會造成距離較遠的節點死亡，若僅考慮能量消耗率因素，又會導致WCV頻繁地在網絡間移動，增加充電延遲和能量耗損。因此，應當同時考慮距離和能量消耗率兩方面因素作為下一個服務節點的選擇指標。假設節點i的能量消耗率在t時刻為Ri(t)，并在一段恒定時間后變為Ri(t＋Δ)。式(23)給出了兩種狀態下的能耗預測模型，即正在充電狀態和未在充電狀態。τ為控制因子(0<τ<1)，τ的取值大小取決于網絡區域大小和節點數量。當節點分布較為稀疏(網絡區域規模較大而節點數量較少)時，τ取較大值，反之則取較小值。Ei(t)為節點i在時間t的剩余能量。本文的能耗預測模型與時間有關，這意味著可以在不同時間預測任何節點的能量變化，節點的能量變化是一個實時過程。式(23)描述如下:

算法2描述了一種基于貪心策略的節點選擇方法。一方面，應當盡可能選擇靠近WCV的節點，以減少WCV在節點間來回運動所產生的額外能耗。另一方面，應當最小化不必要的充電延遲，以保證其他節點可以被及時服務。基于以上考慮，本文提出了一個權值計算公式，綜合考慮兩方面的因素，公式描述如下:

式中:?為控制因子，用以抵消距離的影響。?的值取決于網絡區域的大小和節點數目。當網絡面積較大且節點數量較少時，距離與能耗率之間的數值差異會更大。在這種情況下?將會取一個較小值。本文將所有待服務節點的能耗率降序排序得到Nr，其中第i個節點的能耗率排序值表示為Nr(i)，能耗率越大，則節點的排序值越小。同樣地，將所有待服務節點的距離升序排序得到Nd，最終選擇權值最小的節點作為下一個服務節點。若算法2輸出的下一個服務節點與cschedule當中下一個服務節點不同，則替換為算法2所輸出的節點。根據節點發送的服務請求類型，來決定WCV的具體操作(回收或放置充電裝置)，具體實現如算法2所示。

算法2 基于貪婪策略的服務節點選擇算法

3 實驗仿真

本文對所提出的算法進行了嚴格的模擬來證明它的有效性，首先介紹了各項仿真環境及參數，然后與現有的3種算法進行了仿真結果的對比和分析。為了進行比較，使用2.2中所描述的充電延遲作為性能度量，充電延遲越低的算法被認為是越好的。通過改變SNs的通信范圍、網絡密度、WCV行駛速度、SNs的充電閾值等網絡參數，觀察該算法在不同情況下的表現。

3.1 仿真參數設置

傳感器節點隨機部署在一個220 m×220 m平方米的區域中，該算法的收斂準則為最大迭代次數，將FCFS[17]算法、NJNP[18－19]算法、經典GSA[14]與所提出的算法作對比。在FCFS算法中，來自SNs的充電請求是根據它們到達的先后順序，而NJNP算法則是WCV在考慮充電請求傳入時間順序的基礎上，如果新傳入充電請求的節點距離WCV地理位置更近，則WCV會為新傳入充電請求的節點充電，即新傳入的請求“搶占”了舊請求。考慮到節點是隨機部署的，網絡拓撲結構可能不同。為方便對照，本文對相同的網絡場景取20種不同結果的平均值。假設WCV每次駛離基站前都可以攜帶足夠的充電裝置，且WCV自身所攜帶的電量足夠行駛完一個航程。仿真場景參數如表1所示(可以根據實際的目標應用程序適當放寬參數)。

表1 仿真參數設定

3.2 性能分析

本次實驗對所提出的算法1和FCFS[17]算法、NJNP[18－19]算法以及經典GSA[14]進行了對比仿真分析。在前3 500 round中，四種算法的運行結果分別如圖1。

圖1 四種算法的運行路徑(前3 500 round)

在圖1(a)、1(b)、1(c)和1(d)中，折線所經過路徑上的圓點為待服務節點，其他為正常節點。在折線所經過的圓點當中，空心圓點代表需要放置充電裝置的節點，實心圓點代表需要回收充電裝置的節點。網格圖正中央的小三角形代表基站，折線代表WCV行駛路徑。保持SNs的數量為500，通信距離50 m，充電閾值為0.5 J，WCV行駛速度2 m/s。FCFS算法、NJNP算法、經典GSA和所提出算法的充電延遲分別為267.58 s、227.69 s、192.34 s、166.32 s。FCFS算法、NJNP算法和經典GSA在相比之下有著更長的充電延遲。

接下來分析四種算法在不同場景下的表現。由圖2可以看出，隨著節點通信范圍的增大，通信所耗費的能量增加，FCFS算法的充電延遲明顯增加，NJNP算法由于引入了“搶占”的思想，對充電請求有所優化。經典GSA作為一種智能優化算法，在其適應度函數的構建過程中，充分考慮到了節點在充電過程中空間、時間以及能量等因素，對充電請求進一步優化。因此NJNP算法和經典GSA充電延遲的增長與所提出算法均趨于平穩。當網絡密度增大時，顯而易見，充電請求也會隨之增加，由圖3，圖4可以看出，在較小網絡密度的情況下，四種算法的差異不會很大，但在較大密度的網絡中，FCFS算法的充電延遲明顯增大，而NJNP算法、經典GSA和所提出算法增長較為緩慢，其中所提出的算法的充電延遲最小，更能保證節點壽命的最大化。

圖2 不同通信范圍下的充電延遲

圖3 不同節點數量下的充電延遲

圖4 四種算法的累積充電延遲(5 000 round)

保持節點通信范圍與WCV行駛速度不變，在一定密度的網絡中，隨著充電閾值的升高，需要被服務的節點數目隨之上升，服務請求增加，充電延遲也相應增大。然而閾值的升高卻可以保證節點具有更長的壽命。通常，充電閾值在充電過程中具有一個最佳平衡點，圖5反映了在當前條件下，0.5 J為一個最佳平衡點，當閾值大于0.5 J時，FCFS算法的充電延遲曲線變得陡峭，NJNP算法隨著充電閾值的增大，請求節點也隨之增多，會頻繁執行“搶占”操作，因此充電延遲也有快速上升的趨勢，而經典GSA與所提出的算法則平緩增長，受充電閾值的影響較小，因此更加適合運用于不同需求的WSN當中。在圖6中，四種算法的充電延遲都隨著WCV行駛速度的減慢而增加，因此在惡劣環境的情況下WCV無法以恒定、較快速度行駛時，更加體現了所提出算法的優越性。

圖5 不同充電閾值下的充電延遲

圖6 不同WCV行駛速度下的充電延遲

4 結論

本文研究了多位置并發服務的情形下WCV的規劃調度問題。首先采用線性規劃的方法對WCV的調度問題作出定義，在此基礎上使用改進的引力搜索算法對節點的服務進行按需規劃，有效地延長了網絡壽命。最后，將本文所提出的算法進行大量仿真，并將其與現有的FCFS算法、NJNP算法以及經典GSA進行比較。仿真結果表明，與現有算法相比，所提出的算法顯著地降低了充電延遲，因此，本文所提出的方案具有更大的實際意義和參考價值。