無線可充電傳感器網(wǎng)絡(luò)高效在線充電算法

陳 輝 鄧玉蓮 史雯雋 武繼剛

1(廣東工業(yè)大學(xué) 廣東 廣州 510006) 2(天津工業(yè)大學(xué) 天津 300387)

0 引 言

傳感器網(wǎng)絡(luò)是由大量傳感器節(jié)點(diǎn)組成的自組織網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)具有采集、發(fā)送數(shù)據(jù)的功能。傳感器節(jié)點(diǎn)的電池容量是決定傳感器網(wǎng)絡(luò)生命周期的關(guān)鍵因素之一。近年來，隨著電磁耦合共振無線傳輸技術(shù)的發(fā)展，使得充電設(shè)備能夠通過無線的方式對傳感器節(jié)點(diǎn)進(jìn)行充電，從而延長傳感器網(wǎng)絡(luò)的生命周期。具有供電模塊和無線充電模塊的移動充電設(shè)備MC(Mobile Charger)能夠周期性地為傳感器節(jié)點(diǎn)充電[1-3]。這種包含了移動充電設(shè)備的新型傳感器網(wǎng)絡(luò)被稱為無線可充電傳感器網(wǎng)絡(luò)。

文獻(xiàn)[4]采用經(jīng)典的STP算法證明了充電車按照最短哈密爾頓回路移動方式延長了傳感器網(wǎng)絡(luò)生命周期。文獻(xiàn)[5]結(jié)合傳感器剩余電量和充電車路徑規(guī)劃提出一種新的算法,該算法沒有考慮傳感器通信耗能以及充電轉(zhuǎn)化率問題。文獻(xiàn)[6]將充電策略和通信策略相結(jié)合，使得充電車能夠?yàn)閭鞲衅鞒潆姴⒛苁占瘋鞲衅鳟a(chǎn)生的數(shù)據(jù)。該方式降低了數(shù)據(jù)的傳輸耗能，并將耗能大的傳感器節(jié)點(diǎn)作為待充電節(jié)點(diǎn)，但在動態(tài)充電請求的網(wǎng)絡(luò)環(huán)境中并不適用。文獻(xiàn)[7]將整個傳感器網(wǎng)絡(luò)劃分為幾個子網(wǎng)絡(luò)，在每個子網(wǎng)絡(luò)中選取固定位置定期為傳感器提供能量補(bǔ)給，同時提出一種分布式算法用于調(diào)整鏈路調(diào)度和數(shù)據(jù)收發(fā)速率，以提高傳感器網(wǎng)絡(luò)的整體效用。為了提高網(wǎng)絡(luò)充電效率，文獻(xiàn)[8]提出點(diǎn)對多充電方式，即一個充電車可以為一定范圍內(nèi)的充電車同時充電，但其僅僅提高同一時間內(nèi)傳感器充電數(shù)量，并沒有考慮到單個充電車無法滿足大規(guī)模網(wǎng)絡(luò)能量需求情況。文獻(xiàn)[1]采用K-means聚類算法將傳感器網(wǎng)絡(luò)劃分為若干子區(qū)域，對于每個區(qū)域分派一輛充電車為該區(qū)域節(jié)點(diǎn)充電，有效地滿足了大規(guī)模傳感器網(wǎng)絡(luò)能量需求，但多個充電車同時工作對網(wǎng)絡(luò)負(fù)載和容錯率要求較高。文獻(xiàn)[9]研究充電車速度對整體網(wǎng)絡(luò)能量供給的影響，在已確定的充電路徑和具體充電時間內(nèi)，指派充電車選取適當(dāng)速度以達(dá)到充電延遲和移動延遲的平衡，但是該充電策略無法對新發(fā)送充電請求的傳感器節(jié)點(diǎn)提供電量補(bǔ)給。文獻(xiàn)[10]采用多個充電車為傳感器節(jié)點(diǎn)充電以維持傳感器節(jié)點(diǎn)永久運(yùn)行，多個充電車同時工作可以減少移動距離帶來的額外能量損耗，但對于充電車的路徑選取并沒有實(shí)現(xiàn)最短路徑規(guī)劃。文獻(xiàn)[11]根據(jù)傳感器節(jié)點(diǎn)剩余電量將充電請求分為緊迫請求和一般請求。充電車先對緊迫請求傳感器進(jìn)行充電，一般請求的節(jié)點(diǎn)的剩余電量可以支持到下一輪充電。由此保障WRSNs有最大數(shù)量的節(jié)點(diǎn)正常運(yùn)行。文獻(xiàn)[12]對無線可充電傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)劃分聚類，采用基于旅行商問題的最小生成樹算法求解WRSNs的最大充電吞吐量問題，該方案延長了傳感器網(wǎng)絡(luò)生命周期，但沒有考慮充電車攜帶電量及充電車移動耗能對整體路徑規(guī)劃的影響。文獻(xiàn)[13]在無線可充電傳感器網(wǎng)絡(luò)充電調(diào)度策略中考慮了充電車移動耗能及攜帶電量，但該網(wǎng)絡(luò)的充電調(diào)度策略是基于靜態(tài)網(wǎng)絡(luò)環(huán)境，即充電車在當(dāng)前充電過程中接收到新的充電請求將作為下一個充電周期的待充電傳感器節(jié)點(diǎn)。文獻(xiàn)[14]研究了基于動態(tài)請求的無線可充電傳感器網(wǎng)絡(luò)，即充電車在執(zhí)行充電任務(wù)的過程中同時接收并處理新的請求充電，新請求的出現(xiàn)可能會改變充電車路徑。

本文研究基于動態(tài)請求的無線可充電傳感器網(wǎng)絡(luò)中充電車的充電任務(wù)調(diào)度策略，同時考慮充電車移動耗能和充電周期總電量對充電車路徑規(guī)劃的影響。本文提出一個基于貪心策略和一個基于聚類思想的在線算法規(guī)劃充電車充電路徑，實(shí)現(xiàn)網(wǎng)絡(luò)中充電傳感器數(shù)量的最大化。

本文的貢獻(xiàn)點(diǎn)如下：

(1) 針對動態(tài)請求的無線可充電傳感器網(wǎng)絡(luò)，在充電車移動耗能和充電周期總電量兩個約束條件下的充電傳感器數(shù)量最大化問題，建立非線性整型數(shù)學(xué)模型。

(2) 提出一個基于貪心策略的在線算法。該算法選擇距離充電車最近的傳感器作為下一個充電節(jié)點(diǎn)，因此能夠快速地規(guī)劃充電車的充電路徑。

(3) 基于聚類思想，提出另一個在線算法。該算法采用基于旅行商問題的最小生成樹算法使得充電車在每個類中的充電路徑構(gòu)成一條回路的同時，減少移動耗能。

1 模型與問題定義

1.1 WRSNs 網(wǎng)絡(luò)模型

如圖1所示，WRSNs由若干個同構(gòu)傳感器節(jié)點(diǎn)、一個基站BS(Base Station)和一個充電車組成。正方形塊表示傳感器節(jié)點(diǎn)，用集合V={v1,v2,…,vn}表示。黑色正方形塊表示發(fā)出充電請求的節(jié)點(diǎn)。每個傳感器節(jié)點(diǎn)都配有無線發(fā)射器，能夠給基站和充電車發(fā)送數(shù)據(jù)和充電請求信號。基站負(fù)責(zé)匯總、處理傳感器的監(jiān)測數(shù)據(jù)，調(diào)整充電車充電策略以及為充電車補(bǔ)充電量。充電車是一個搭載有供電塊和無線收發(fā)器模塊的移動充電設(shè)備。在充電過程中充電車可以接收充電請求信號，調(diào)整自身移動路徑。WRSNs中采用點(diǎn)對點(diǎn)方式對傳感器節(jié)點(diǎn)進(jìn)行充電，即充電車在同一時刻位于特定位置通過電磁耦合共振技術(shù)將電量傳輸給單個傳感器節(jié)點(diǎn)。初始狀態(tài)下充電車位于基站。

圖1 WRSNs充電示例圖

Bi表示傳感器節(jié)點(diǎn)vi的電池容量，當(dāng)節(jié)點(diǎn)vi的剩余電量低于預(yù)定閾值Mi=α·Bi(0<α<1)時會向基站和充電車發(fā)送充電請求信號，即ci=(vi,REi,ri)，REi表示節(jié)點(diǎn)vi剩余電量，ri表示節(jié)點(diǎn)剩余時間。待充電集合Vc用來存放請求充電服務(wù)的節(jié)點(diǎn)，當(dāng)充電車收到來自傳感器節(jié)點(diǎn)vi的充電請求后，將節(jié)點(diǎn)vi放入待充電集合Vc中。

充電車是依靠電量提供動力支持移動的充電設(shè)備。在執(zhí)行充電任務(wù)過程中，充電車根據(jù)接收到的充電請求信號為傳感器節(jié)點(diǎn)提供充電服務(wù)。WRSNs中周期性指派充電車為傳感器節(jié)點(diǎn)充電，用T表示充電周期時間。基站在一個充電周期T內(nèi)為充電車提供的總電量為E，稱為充電周期總電量。基站和充電車接收到充電請求后，充電車攜帶滿電量Em從基站出發(fā)給傳感器節(jié)點(diǎn)充電，其中Em為充電車電池容量，Em≤E。在充電周期T內(nèi)，充電車自身移動和為傳感器節(jié)點(diǎn)充電都會消耗其電量，因此當(dāng)充電車電量不能滿足待充電傳感器所需電量時，充電車返回基站蓄電，蓄滿電后再從基站出發(fā)執(zhí)行充電任務(wù)。充電車在每一個充電周期T內(nèi)可能多次返回基站蓄電。本文采用點(diǎn)對點(diǎn)的充電方式，即WRSNs中只有一個充電車為傳感器提供充電服務(wù)，為了保障WRSNs中下一個充電周期能夠順利進(jìn)行，充電車在每個充電周期T內(nèi)需要滿足兩個條件：充電車要在充電周期T內(nèi)回到基站；充電車最終有足夠電量回到基站。

1.2 最大充電傳感器數(shù)

最大充電傳感器數(shù)是指在一個充電周期T內(nèi)，充電車能夠充電的最大傳感器數(shù)目。

傳感器節(jié)點(diǎn)因電量耗盡停止工作會影響整體WRSNs運(yùn)行，為了保證WRSNs中有最大數(shù)量的傳感器正常運(yùn)作，優(yōu)先對低于預(yù)定閾值的傳感器節(jié)點(diǎn)充電。本文的目標(biāo)是在每一次充電周期T中最大化充電傳感器數(shù)量，以達(dá)到延長無線傳感器網(wǎng)絡(luò)生命周期的目的。

1.3 問題定義

本節(jié)使用的主要符號及其定義如表1所示。

待充電節(jié)點(diǎn)向基站發(fā)送充電請求，基站派出帶有滿電量Em的充電車為傳感器節(jié)點(diǎn)充電。每一個傳感器節(jié)點(diǎn)所需電量為常數(shù)L。在執(zhí)行充電任務(wù)的過程中充電車根據(jù)接收到的新充電請求信號改變充電路徑，充電車移動和為傳感器節(jié)點(diǎn)充電將會消耗自身電量。

表1 符號及其定義

最大充電傳感器數(shù)：

(1)

xi,j∈(0,1)i,j=0,1,…,n

(2)

式中：xi,j=0時，充電車沒有經(jīng)過邊xi,j，即充電車沒有訪問vj；xi,j=1時，充電車經(jīng)過邊xi,j，即充電車為節(jié)點(diǎn)vj充電。

為了確保充電車每次執(zhí)行充電任務(wù)時必須基站出發(fā)，最后回到基站，有如下約束條件：

(3)

式中不等式取值大于等于1表示在一個充電周期T內(nèi)，充電車多次往返基站。

為了確保在每次充電周期中，只能向待充電的傳感器節(jié)點(diǎn)提供至多一次充電服務(wù)，有如下約束條件：

(4)

為了確保充電車充電消耗時間不超過充電周期T，有如下約束條件：

(5)

為了確保充電車充電消耗時間不超過充電周期T，有如下約束條件：

(6)

最大充電傳感器數(shù)問題目標(biāo)函數(shù)可表示為如下非線性0-1整型規(guī)劃問題：

(7)

定理1無線可充電傳感器網(wǎng)絡(luò)求解最大充電傳感器數(shù)量問題是NP-hard問題。

證明：文獻(xiàn)[12]研究的是充電車的最大充電吞吐量，該問題是NP-hard問題。該問題描述如下：在一定規(guī)模的傳感器網(wǎng)絡(luò)中存在n個待充電的傳感器節(jié)點(diǎn)，充電車服務(wù)時間T內(nèi)從基站出發(fā)最后返回基站期間所能提供充電服務(wù)的節(jié)點(diǎn)數(shù)。因此，充電車的目標(biāo)為，在服務(wù)時間內(nèi)找到一條最佳的充電任務(wù)路徑，使得充電車實(shí)現(xiàn)最大的充電服務(wù)吞吐量。本文增加了充電車移動耗能和充電周期總電量兩個約束條件，復(fù)雜化了充電車充電傳感器數(shù)量最大化問題。NP-hard問題描述如下，在歐幾里得平面上存在n個節(jié)點(diǎn)，每個節(jié)點(diǎn)具有相應(yīng)的值，節(jié)點(diǎn)與節(jié)點(diǎn)的邊有權(quán)值。要求找到一條路徑從1節(jié)點(diǎn)出發(fā)遍歷平面上的n個節(jié)點(diǎn)使得節(jié)點(diǎn)值之和最大且所經(jīng)過的邊權(quán)值之和不能超過約束值。在約束值范圍內(nèi)平面內(nèi)的所有節(jié)點(diǎn)不一定都能被訪問，每個節(jié)點(diǎn)至多只能被訪問一次。在靜態(tài)的無線可充電傳感器網(wǎng)絡(luò)充電車充電任務(wù)調(diào)度問題中，待充電集合Vc中待充電傳感節(jié)點(diǎn)相當(dāng)于歐幾里得平面上存在的n個節(jié)點(diǎn)；充電路徑中訪問的傳感器節(jié)點(diǎn)等同于遍歷1至n節(jié)點(diǎn)；傳感器網(wǎng)絡(luò)中充電車總路徑消耗不能超過時間T和總電量E等同于定向問題中所經(jīng)過的邊權(quán)值之和不能超過約束值。綜上所述，充電車實(shí)現(xiàn)最大充電傳感器數(shù)目等同于求解定向運(yùn)動問題。動態(tài)充電請求網(wǎng)絡(luò)是靜態(tài)無線可充電傳感器網(wǎng)絡(luò)的一種特殊情況。因此，動態(tài)充電請求網(wǎng)絡(luò)下求解最大充電傳感器數(shù)是NP-hard問題。

2 算 法

2.1 Online_Greedy算法

本文首先提出一個實(shí)時的Online_Greedy算法。Online_Greedy算法運(yùn)用貪心思想規(guī)劃充電車移動路線，總是尋找距離當(dāng)前節(jié)點(diǎn)服務(wù)時間最短的節(jié)點(diǎn)加入充電路徑。如圖2所示，Online_Greedy算法是在一個充電周期T內(nèi)，充電車從基站出發(fā)選擇距離基站服務(wù)時間最短的節(jié)點(diǎn)為第一個充電節(jié)點(diǎn)，隨后每一個納入充電路徑的節(jié)點(diǎn)都是距離當(dāng)前充電節(jié)點(diǎn)服務(wù)時間最短的傳感器節(jié)點(diǎn)。

圖2 Online_Greedy算法充電策略示意圖

在WRSNs網(wǎng)絡(luò)中，假設(shè)充電車當(dāng)前充電節(jié)點(diǎn)為vi，下一個充電節(jié)點(diǎn)為vj。我們用Qj表示節(jié)點(diǎn)vj的服務(wù)時間。節(jié)點(diǎn)vj的服務(wù)時間為單個傳感器充電時間C、從節(jié)點(diǎn)vi移動到節(jié)點(diǎn)vj的時間tij、從當(dāng)前vj節(jié)點(diǎn)返回基站時間tj0三者時間之和, 即Qj=C+tij+tj0。用Wj表示節(jié)點(diǎn)vj的服務(wù)耗電量，節(jié)點(diǎn)vj的服務(wù)耗電量為單個傳感器充電的電量L、從節(jié)點(diǎn)vi移動到節(jié)點(diǎn)vj的耗電eij、從當(dāng)前vj節(jié)點(diǎn)返回基站的移動耗電ej0三者時間之和，即Wj=L+eij+ej0。

圖2中實(shí)線箭頭區(qū)域表示充電車第一段充電路徑。充電車為下一個節(jié)點(diǎn)提供充電服務(wù)前，會計(jì)算自身剩余電量是否能夠?yàn)橄乱粋€節(jié)點(diǎn)充電以及支撐其返回基站。若電量充足，充電車?yán)^續(xù)為傳感器節(jié)點(diǎn)充電，反之充電車就返回基站蓄電，然后進(jìn)行下一輪的充電。圖2虛線箭頭部分表示充電車返回基站蓄電后再次出發(fā)的第二段充電路徑。表2為算法描述中符號和函數(shù)定義。

表2 算法符號和函數(shù)定義

Online_Greedy算法描述如算法1所示。在充電時間T和總電量E內(nèi)Online_Greedy算法求解無線傳感器網(wǎng)絡(luò)最大充電傳感器數(shù)量的時間復(fù)雜度為O(n)。

算法1Online_Greedy算法

輸入:一個等待充電的傳感器集合Vc,充電周期T,充電周期總電量E輸出:始點(diǎn)為v0的充電路徑P1: cur=v0;2: t=0;3: path_cost=0;4: while tE(t+time(cur, next)) ≤ T14: path_cost=0;/?返回基站?/15: else16: break;17: return P.

2.2 Online_MST_Cluster算法

實(shí)際環(huán)境中，傳感器節(jié)點(diǎn)的分布可能會按照不同的區(qū)域集中分布，針對這種情況，本文基于聚類思想并加入了充電車移動耗能和總電量的限制，提出了Online_MST_Cluster算法。

Online_MST_Cluster算法先對當(dāng)前待充電的傳感器節(jié)點(diǎn)劃分聚類，再計(jì)算生成的子聚類中所有的傳感器節(jié)點(diǎn)實(shí)現(xiàn)全部充電所消耗的時間和電量，當(dāng)充電的時間和電量消耗滿足限制條件時，充電車從基站出發(fā)為該聚類充電，充電完成后返回基站，在充電時間T內(nèi)反復(fù)迭代上述過程。

Online_Greedy算法是對單個節(jié)點(diǎn)提供充電服務(wù)，而在Online_MST_Cluster算法中，充電車為聚類內(nèi)包含的所有傳感器節(jié)點(diǎn)提供充電服務(wù)。Online_MST_Cluster算法的充電模型如圖3所示。

圖3 Online_MST_Cluster算法充電策略示意圖

綜上，Online_MST_Cluster算法是采用聚類迭代循環(huán)的方式尋找滿足充電條件的傳感器聚類。首先，充電車從基站出發(fā)，在已經(jīng)劃分好的K個聚類中選擇滿足充電條件的聚類，若存在的聚類無法滿足充電條件時，調(diào)整K值重新劃分聚類數(shù)目，直至出現(xiàn)滿足充電條件的聚類，在已經(jīng)超出時間T的情況下程序迭代將不再進(jìn)行，算法具體描述如算法2所示。

算法2Online_MST_Cluster算法

輸入:一個等待充電的傳感器集合Vc, 充電周期T, 充電周期總電量E, 常數(shù)K輸出:始點(diǎn)為v0的充電路徑P1: Kinit = 1;2: K=Kinit;3: t=0;4: path_cost=0;5: while t < T do6: clusters=K_means(Vc, K) ; /?采用K-Means算法將Vc劃分為K個聚類: V1,V2,…,VK ?/7: paths=MST (clsuters);/? 采用解決旅行商算法問題的最小生成樹算法求得基站v0和每一個聚類最短回路?/8: sorted (clusters, paths) ;/?按照聚類gain值從小到大進(jìn)行排序?/9: for each cluster in clusters10: if cost+cost (cluster) ≤ E andt+t(cluster)≤T11: P←cluster;12: cost+=cost(cluster);13: t+=t(cluster);14: ifno cluster found to charge, then adjust K setting K=min{2K,|Vc|};15: if K==|Vc| and no cluster found to charge16: break;17: update Vc;18: K←Kinit;19: end while ;20: return P.

定理2在給定充電時間T內(nèi)，采用Online_MST_Cluster算法去解決最大充電傳感器數(shù)問題，該算法的時間復(fù)雜度為O(|V|2·lg|V|·T)，|V|是總傳感器數(shù)量。

證明：顯然，Online_MST_Cluster算法能夠求解無線傳感器網(wǎng)絡(luò)最大充電傳感器數(shù)問題，接下來我們分析算法的時間復(fù)雜度。k-means算法的時間復(fù)雜度為O(|Vc|·n)，其中n是k-means算法中的迭代次數(shù)。計(jì)算每個聚類gain時間復(fù)雜度為O(|Vc|2) 。隨著聚類數(shù)K值的調(diào)整，在滿足充電條件聚類中計(jì)算最大的gain值的時間復(fù)雜度為O(|Vc|2·lg|Vc|)。所以很容易證明受到充電時間T影響的算法時間復(fù)雜度為O(|Vc|2·lg|Vc|·T)=O(|V|2·lg|V|·T)，其中|Vc|≤|V|。

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

這一節(jié)將通過5組模擬實(shí)驗(yàn)對比2個算法的性能，實(shí)驗(yàn)的參數(shù)設(shè)置如表3所示。

表3 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)是在固定范圍的監(jiān)測區(qū)域內(nèi)進(jìn)行模擬對比實(shí)驗(yàn)，基站位于監(jiān)測區(qū)域內(nèi)。實(shí)驗(yàn)參數(shù)如表3所示，每一組實(shí)驗(yàn)數(shù)據(jù)對應(yīng)一幅實(shí)驗(yàn)結(jié)果圖。由于不同傳感器作業(yè)任務(wù)不同，傳感器節(jié)點(diǎn)電量低于預(yù)定閾值Mi=α·Bi就向基站和充電車發(fā)送充電請求信號。

本文以一個充電周期T內(nèi)被充電的傳感器數(shù)量的多少來衡量充電算法的性能。

3.1 離線精確算法與兩個在線算法

Offline_Aglo是基于窮舉策略的離線精確算法。我們對比離線精確算法Offline_Aglo與兩個在線算法Online_Greedy、Online_MST_Cluster的執(zhí)行效果。其中離線精確算法Offline_Aglo是基于靜態(tài)充電請求網(wǎng)絡(luò)，而兩個在線算法是基于動態(tài)充電請求網(wǎng)絡(luò)。靜態(tài)充電請求網(wǎng)絡(luò)是每一個充電周期的待充電傳感器節(jié)點(diǎn)都事先給定，充電車在執(zhí)行充電任務(wù)的過程中接收到的新充電請求將作為下一個充電周期的待充電節(jié)點(diǎn)。離線精確算法Offline_Aglo給出當(dāng)前靜態(tài)充電請求網(wǎng)絡(luò)的最優(yōu)解。實(shí)驗(yàn)設(shè)有傳感器節(jié)點(diǎn)數(shù)量為10～50，充電周期T=60 s，總電量E=100 q。

我們對比Offline_Aglo算法與兩個在線算法Online_Greedy、Online_MST_Cluster在小規(guī)模網(wǎng)絡(luò)中實(shí)現(xiàn)的最大充電傳感器數(shù)量。如圖4所示，橫坐標(biāo)表示W(wǎng)RSNs中部署的傳感器節(jié)點(diǎn)數(shù)，縱坐標(biāo)表示充電時間內(nèi)的最大充電傳感器數(shù)。從圖4中可明顯看到Offline_Aglo算法的執(zhí)行效果一直優(yōu)于Online_Greedy和Online_MST_Cluster算法。值得注意的是當(dāng)傳感器節(jié)點(diǎn)超過20個時，Offline_Aglo算法與兩個在線算法之間的差距越來越大，造成這一現(xiàn)象的原因是，Offline_Aglo采用窮舉法且充電周期中待充電傳感器節(jié)點(diǎn)都已知。在實(shí)現(xiàn)最大化充電傳感器數(shù)量問題上，Online_Greedy、Online_MST_Cluster算法與精確算法Offline_Aglo算法相比分別差40%、48%。文獻(xiàn)[13]中Online_SPT、Online_K_Cluster與精確算法Offline_Appro分別差59%、51%。在小規(guī)模網(wǎng)絡(luò)中，基于所有待充電傳感器節(jié)點(diǎn)都已知的情況下，Offline_Aglo算法是最好的選擇。然而，Offline_Aglo算法代價大，運(yùn)行時間長，不適用于大規(guī)模的無線可充電傳感器網(wǎng)絡(luò)。

T=60 s E=100 q圖4 離線算法和兩個在線算法執(zhí)行效果圖

3.2 無線可充電傳感器網(wǎng)絡(luò)規(guī)模

這一小節(jié)對比Online_Greedy算法和Online_MST_Cluster算法在不同的無線可充電傳感網(wǎng)絡(luò)規(guī)模下充電周期內(nèi)的最大充電傳感器數(shù)。充電周期T=2 500 s, 總電量E=1 500 q, 傳感器節(jié)點(diǎn)數(shù)300～750。

實(shí)驗(yàn)結(jié)果如圖5(a)所示，從圖中可知Online_MST_Cluster算法充電周期內(nèi)的充電傳感器數(shù)量一直明顯優(yōu)于Online_SPT算法。當(dāng)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù)量在300到500時，Online_Greedy算法充電周期內(nèi)所充電的傳感器數(shù)量波動較大，這是因?yàn)镺nline_Greedy選取的第一個充電節(jié)點(diǎn)會對后面的實(shí)驗(yàn)結(jié)果產(chǎn)生較大的影響。Online_MST_Cluster算法執(zhí)行效果增長穩(wěn)定。隨著網(wǎng)絡(luò)中傳感器數(shù)量逐漸增大，Online_Greedy算法、Online_MST_Cluster算法實(shí)現(xiàn)充電的傳感器數(shù)量分別占總待充電傳感器數(shù)量67%、76%。

(a) T=1 500 s E=2 500 q

(b) T=3 000 s E=3 000 q圖5 網(wǎng)絡(luò)規(guī)模與最大充電傳感器數(shù)

為了對比Online_Greedy算法和Online_MST_Cluster算法在大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)下的執(zhí)行效果，實(shí)驗(yàn)繼續(xù)擴(kuò)大無線傳感器網(wǎng)絡(luò)規(guī)模，充電周期T=3 000 s，總電量E=3 000 q，傳感器節(jié)點(diǎn)數(shù)750～1 200。 實(shí)驗(yàn)結(jié)果如圖5 (b)所示，當(dāng)傳感器節(jié)點(diǎn)數(shù)在800到900時,Online_Greedy算法充電周期內(nèi)實(shí)現(xiàn)的最大充電傳感器數(shù)要大于Online_MST_Cluster算法。隨著網(wǎng)絡(luò)規(guī)模逐漸增大，Online_Greedy算法效果多次呈現(xiàn)上升后下降而后又上升的趨勢，這是由于采用貪心策略規(guī)劃充電車的充電路徑，造成實(shí)驗(yàn)效果波動較大。Online_MST_Cluster算法一直處于穩(wěn)定上升的狀態(tài)，這是因?yàn)镺nline_MST_Cluster是先聚類后充電，每一次迭代都計(jì)算所消耗的時間及電量，因此實(shí)驗(yàn)效果比較穩(wěn)定。當(dāng)傳感器節(jié)點(diǎn)數(shù)超過1 050時 ，Online_MST_Cluster算法執(zhí)行效果明顯優(yōu)于Online_Greedy算法。

3.3 總電量

這一小節(jié)將研究充電車攜帶電量E對充電周期內(nèi)實(shí)現(xiàn)最大充電傳感器數(shù)的影響。如圖6(a)所示，充電時間T=1 500 s，傳感器節(jié)點(diǎn)數(shù)為1 500，總電量值范圍700～1 600。隨著總電量不斷增大，兩個算法充電時間內(nèi)實(shí)現(xiàn)的最大充電傳感器數(shù)呈緩慢增長的趨勢。當(dāng)E值范圍在700～1 400時，Online_Greedy算法執(zhí)行效果優(yōu)于Online_MST_Cluster算法，隨著總電量繼續(xù)增大，Online_Greedy算法的執(zhí)行效果呈現(xiàn)不穩(wěn)定狀態(tài)，而Online_MST_Cluster算法一直處于穩(wěn)定上升狀態(tài)，最終在總電量E=1 400時超越Online_Greedy算法。

(a) T=1 500 s sensor_num=1 500

(b) T=3 000 s sensor_num=200圖6 E與最大充電傳感器數(shù)

同樣地，我們繼續(xù)增大總電量E值，觀察電量大小對實(shí)驗(yàn)結(jié)果的影響，在圖6(b)中，充電時間為T=3 000 s，傳感器數(shù)量為2 000，總電量E值范圍500～3 500。從圖中可知Online_Greedy在充電周期內(nèi)實(shí)現(xiàn)的最大充電傳感器數(shù)波動較大，Online_MST_Cluster充電周期內(nèi)實(shí)現(xiàn)的最大充電傳感器數(shù)呈穩(wěn)步增長趨勢，當(dāng)充電車攜帶電量較低時，Online_MST_Cluster算法效果不如Online_Greedy算法，但隨著總電量的持續(xù)增大，Online_MST_Cluster算法的實(shí)驗(yàn)結(jié)果是優(yōu)于Online_Greedy算法。 本文考慮了充電車移動耗能和總電量對充電周期內(nèi)最大充電傳感器數(shù)的影響，四組實(shí)驗(yàn)結(jié)果表明，Online_Greedy算法執(zhí)行效果穩(wěn)定性較差，波動較大。而Online_MST_Cluster算法執(zhí)行效果穩(wěn)定，隨著網(wǎng)絡(luò)規(guī)模和總電量增加，充電時間內(nèi)的最大充電傳感器數(shù)目也穩(wěn)定增長，所以O(shè)nline_MST_Cluster算法是求解閉合無線傳感器網(wǎng)絡(luò)最大充電傳感器數(shù)問題的一種理想的解決方案。

4 結(jié) 語

本文研究動態(tài)請求的無線可充電傳感器網(wǎng)絡(luò)中最大充電傳感器數(shù)問題，提出Online_Greedy和Online_MST_Cluster算法解決充電周期內(nèi)如何實(shí)現(xiàn)最大化充電無線傳感器數(shù)。考慮了充電車移動耗能和充電周期內(nèi)總電量兩個因素。其中，Online_Greedy算法時間復(fù)雜度低，運(yùn)行效率高，Online_Greedy算法在大規(guī)模的無線傳感器網(wǎng)絡(luò)中執(zhí)行效果穩(wěn)定性較差，在小型的無線傳感器網(wǎng)絡(luò)中反而獲得較高的效率。Online_MST_Cluster算法采用聚類劃分的充電方式，不再單獨(dú)處理單個傳感器節(jié)點(diǎn)充電請求，而是對一個聚類中待充電傳感器節(jié)點(diǎn)進(jìn)行充電，大大減少了移動電量消耗。Online_MST_Cluster算法效果穩(wěn)定，在大規(guī)模無線傳感器網(wǎng)絡(luò)中應(yīng)用較好。在未來的工作中我們將重點(diǎn)研究充電車的充電路徑調(diào)度策略，提高充電車攜帶電量，采用更新穎的聚類劃分方式，來實(shí)現(xiàn)充電周期內(nèi)最大充電傳感器數(shù)量。