一種移動充電器對無線傳感器節(jié)點充電的調(diào)度模型?

神顯豪郭 泰牛少華張烈平

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

傳統(tǒng)無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)的壽命常常被節(jié)點(Sensor Nodes，SNs)的能量瓶頸所制約[1]。盡管許多研究人員在節(jié)能方面做出了很大的努力，有限的能量仍然是WSN長期運行的瓶頸[2]。為了延長SNs的有效壽命，現(xiàn)有的研究主要考慮使用無線能量傳輸?shù)姆椒▽o線傳感器節(jié)點進行能量補充[3]。無線能量傳輸?shù)闹饕枷胧抢秒姶判?yīng)或磁諧振耦合對SNs進行充電。基于無線能量傳輸?shù)某潆姺桨钢饕譃閮深?，即周期性充電方案[4]和按需充電方案[5]。Hu等人[6]研究了基于多充電器的周期性充電時間規(guī)劃和充電路徑規(guī)劃問題。Dai[7]等人針對移動充電器在大規(guī)模無線傳感器網(wǎng)絡(luò)中不能有效的工作的問題，提出了一種周期性充電的近似算法。Lyu等人[8]提出了一種基于有限移動能量的周期性充電方案，這種方案根據(jù)節(jié)點能量的周期性變化對節(jié)點進行充電。由于節(jié)點的能耗具有很大的不確定性，因此這種方案并不適合具有動態(tài)變化的大規(guī)?？沙潆姛o線傳感器網(wǎng)絡(luò)。按需充電方案是只有當(dāng)節(jié)點的能量水平低于給定閾值發(fā)出充電請求，基站接收到請求后安排無線充電車(Wireless Charging Vehicle，WCV)對節(jié)點充電。Lyes Khelladi[9]提出了一種基于分組請求的按需充電模式。Dong[10]提出了一種通過節(jié)點位置、剩余能量、歷史貢獻來選擇按需充電節(jié)點的方案。Jiang[11]提出了一種新穎地根據(jù)節(jié)點充電請求自由移動充電裝置的充電方案。

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

1 系統(tǒng)模型

1.1 無線傳感器網(wǎng)絡(luò)模型

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

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

1.2 多約束線性規(guī)劃的無線充電車調(diào)度模型

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

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

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

目標:最小化cdelay

約束條件如式(4):

式中:?i:1≤i≤N，N為節(jié)點總數(shù)，cradius為充電半徑。

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

2 基于改進引力搜索算法的節(jié)點服務(wù)規(guī)劃算法

2.1 經(jīng)典引力搜索算法

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

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

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

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

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

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

2.2 適應(yīng)度函數(shù)的構(gòu)建

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

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

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

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

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

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

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

式中:?Si∈Cschedule。

當(dāng)WSN中的充電延遲降低時，被充電的節(jié)點會顯著增加，則WSN工作壽命也會隨之增加，因此選擇充電延遲作為適應(yīng)度函數(shù)，即:

2.3 基于改進引力搜索算法的節(jié)點服務(wù)規(guī)劃算法

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

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

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

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

式中:t為當(dāng)前迭代次數(shù)。對于每個重質(zhì)點，以其當(dāng)前位置(定義如式(9))為圓心，R為半徑作一圓形區(qū)域。在該區(qū)域內(nèi)，重質(zhì)點對其他輕質(zhì)點產(chǎn)生引力，根據(jù)式(5)和式(6)，重質(zhì)點對其他輕質(zhì)點產(chǎn)生的引力定義為式(20):

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

同樣地，若輕質(zhì)點在上述圓形區(qū)域外，則重質(zhì)點對輕質(zhì)點產(chǎn)生斥力，根據(jù)式(9)，斥力可以定義為:

算法運行時，首先初始化一個變量gfit，以存儲目前為止找到的最優(yōu)服務(wù)計劃的適應(yīng)度函數(shù)值。同樣地，初始化一個變量gbest用于存儲這些充電計劃的位置向量。在不滿足終止條件前，反復(fù)更新G(t)、best(t)、worst(t)、Kbest的質(zhì)量，質(zhì)點的速度、加速度和位置。定義rqueue為發(fā)送請求的ID數(shù)組，round為所有SNs將數(shù)據(jù)傳輸?shù)交疽淮嗡枰臅r間。通常，充電延遲越小的質(zhì)點性能越好，因此其質(zhì)量也就越大。具體算法實現(xiàn)如算法1所示。

算法1 基于改進GSA的服務(wù)計劃生成算法

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

算法2描述了一種基于貪心策略的節(jié)點選擇方法。一方面，應(yīng)當(dāng)盡可能選擇靠近WCV的節(jié)點，以減少WCV在節(jié)點間來回運動所產(chǎn)生的額外能耗。另一方面，應(yīng)當(dāng)最小化不必要的充電延遲，以保證其他節(jié)點可以被及時服務(wù)?；谝陨峡紤]，本文提出了一個權(quán)值計算公式，綜合考慮兩方面的因素，公式描述如下:

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

算法2 基于貪婪策略的服務(wù)節(jié)點選擇算法

3 實驗仿真

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

3.1 仿真參數(shù)設(shè)置

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

表1 仿真參數(shù)設(shè)定

3.2 性能分析

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

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

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

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

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

圖3 不同節(jié)點數(shù)量下的充電延遲

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

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

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

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

4 結(jié)論

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