無線可充電傳感器網(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è)備能夠通過無線的方式對(duì)傳感器節(jié)點(diǎn)進(jìn)行充電，從而延長(zhǎng)傳感器網(wǎng)絡(luò)的生命周期。具有供電模塊和無線充電模塊的移動(dòng)充電設(shè)備MC(Mobile Charger)能夠周期性地為傳感器節(jié)點(diǎn)充電[1-3]。這種包含了移動(dòng)充電設(shè)備的新型傳感器網(wǎng)絡(luò)被稱為無線可充電傳感器網(wǎng)絡(luò)。

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

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

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

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

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

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

1 模型與問題定義

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

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

圖1 WRSNs充電示例圖

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

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

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

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

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

1.3 問題定義

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

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

表1 符號(hào)及其定義

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

(5)

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

2 算 法

2.1 Online_Greedy算法

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

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

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

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

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

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

算法1Online_Greedy算法

輸入:一個(gè)等待充電的傳感器集合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)的分布可能會(huì)按照不同的區(qū)域集中分布，針對(duì)這種情況，本文基于聚類思想并加入了充電車移動(dòng)耗能和總電量的限制，提出了Online_MST_Cluster算法。

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

Online_Greedy算法是對(duì)單個(gè)節(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個(gè)聚類中選擇滿足充電條件的聚類，若存在的聚類無法滿足充電條件時(shí)，調(diào)整K值重新劃分聚類數(shù)目，直至出現(xiàn)滿足充電條件的聚類，在已經(jīng)超出時(shí)間T的情況下程序迭代將不再進(jìn)行，算法具體描述如算法2所示。

算法2Online_MST_Cluster算法

輸入:一個(gè)等待充電的傳感器集合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個(gè)聚類: V1,V2,…,VK ?/7: paths=MST (clsuters);/? 采用解決旅行商算法問題的最小生成樹算法求得基站v0和每一個(gè)聚類最短回路?/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在給定充電時(shí)間T內(nèi)，采用Online_MST_Cluster算法去解決最大充電傳感器數(shù)問題，該算法的時(shí)間復(fù)雜度為O(|V|2·lg|V|·T)，|V|是總傳感器數(shù)量。

證明：顯然，Online_MST_Cluster算法能夠求解無線傳感器網(wǎng)絡(luò)最大充電傳感器數(shù)問題，接下來我們分析算法的時(shí)間復(fù)雜度。k-means算法的時(shí)間復(fù)雜度為O(|Vc|·n)，其中n是k-means算法中的迭代次數(shù)。計(jì)算每個(gè)聚類gain時(shí)間復(fù)雜度為O(|Vc|2) 。隨著聚類數(shù)K值的調(diào)整，在滿足充電條件聚類中計(jì)算最大的gain值的時(shí)間復(fù)雜度為O(|Vc|2·lg|Vc|)。所以很容易證明受到充電時(shí)間T影響的算法時(shí)間復(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)對(duì)比2個(gè)算法的性能，實(shí)驗(yàn)的參數(shù)設(shè)置如表3所示。

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

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

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

3.1 離線精確算法與兩個(gè)在線算法

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

我們對(duì)比Offline_Aglo算法與兩個(gè)在線算法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)表示充電時(shí)間內(nèi)的最大充電傳感器數(shù)。從圖4中可明顯看到Offline_Aglo算法的執(zhí)行效果一直優(yōu)于Online_Greedy和Online_MST_Cluster算法。值得注意的是當(dāng)傳感器節(jié)點(diǎn)超過20個(gè)時(shí)，Offline_Aglo算法與兩個(gè)在線算法之間的差距越來越大，造成這一現(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算法代價(jià)大，運(yùn)行時(shí)間長(zhǎng)，不適用于大規(guī)模的無線可充電傳感器網(wǎng)絡(luò)。

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

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

這一小節(jié)對(duì)比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時(shí)，Online_Greedy算法充電周期內(nèi)所充電的傳感器數(shù)量波動(dòng)較大，這是因?yàn)镺nline_Greedy選取的第一個(gè)充電節(jié)點(diǎn)會(huì)對(duì)后面的實(shí)驗(yàn)結(jié)果產(chǎn)生較大的影響。Online_MST_Cluster算法執(zhí)行效果增長(zhǎng)穩(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ù)

為了對(duì)比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時(shí),Online_Greedy算法充電周期內(nèi)實(shí)現(xiàn)的最大充電傳感器數(shù)要大于Online_MST_Cluster算法。隨著網(wǎng)絡(luò)規(guī)模逐漸增大，Online_Greedy算法效果多次呈現(xiàn)上升后下降而后又上升的趨勢(shì)，這是由于采用貪心策略規(guī)劃充電車的充電路徑，造成實(shí)驗(yàn)效果波動(dòng)較大。Online_MST_Cluster算法一直處于穩(wěn)定上升的狀態(tài)，這是因?yàn)镺nline_MST_Cluster是先聚類后充電，每一次迭代都計(jì)算所消耗的時(shí)間及電量，因此實(shí)驗(yàn)效果比較穩(wěn)定。當(dāng)傳感器節(jié)點(diǎn)數(shù)超過1 050時(shí) ，Online_MST_Cluster算法執(zhí)行效果明顯優(yōu)于Online_Greedy算法。

3.3 總電量

這一小節(jié)將研究充電車攜帶電量E對(duì)充電周期內(nèi)實(shí)現(xiàn)最大充電傳感器數(shù)的影響。如圖6(a)所示，充電時(shí)間T=1 500 s，傳感器節(jié)點(diǎn)數(shù)為1 500，總電量值范圍700～1 600。隨著總電量不斷增大，兩個(gè)算法充電時(shí)間內(nèi)實(shí)現(xiàn)的最大充電傳感器數(shù)呈緩慢增長(zhǎng)的趨勢(shì)。當(dāng)E值范圍在700～1 400時(shí)，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時(shí)超越Online_Greedy算法。

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

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

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

4 結(jié) 語

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