無線可充電傳感器網絡高效在線充電算法

陳 輝 鄧玉蓮 史雯雋 武繼剛

1(廣東工業大學 廣東 廣州 510006) 2(天津工業大學 天津 300387)

0 引 言

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

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

本文研究基于動態請求的無線可充電傳感器網絡中充電車的充電任務調度策略，同時考慮充電車移動耗能和充電周期總電量對充電車路徑規劃的影響。本文提出一個基于貪心策略和一個基于聚類思想的在線算法規劃充電車充電路徑，實現網絡中充電傳感器數量的最大化。

本文的貢獻點如下：

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

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

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

1 模型與問題定義

1.1 WRSNs 網絡模型

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

圖1 WRSNs充電示例圖

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

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

1.2 最大充電傳感器數

最大充電傳感器數是指在一個充電周期T內，充電車能夠充電的最大傳感器數目。

傳感器節點因電量耗盡停止工作會影響整體WRSNs運行，為了保證WRSNs中有最大數量的傳感器正常運作，優先對低于預定閾值的傳感器節點充電。本文的目標是在每一次充電周期T中最大化充電傳感器數量，以達到延長無線傳感器網絡生命周期的目的。

1.3 問題定義

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

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

表1 符號及其定義

最大充電傳感器數：

(1)

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

(2)

式中：xi,j=0時，充電車沒有經過邊xi,j，即充電車沒有訪問vj；xi,j=1時，充電車經過邊xi,j，即充電車為節點vj充電。

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

(3)

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

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

(4)

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

(5)

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

(6)

最大充電傳感器數問題目標函數可表示為如下非線性0-1整型規劃問題：

(7)

定理1無線可充電傳感器網絡求解最大充電傳感器數量問題是NP-hard問題。

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

2 算 法

2.1 Online_Greedy算法

本文首先提出一個實時的Online_Greedy算法。Online_Greedy算法運用貪心思想規劃充電車移動路線，總是尋找距離當前節點服務時間最短的節點加入充電路徑。如圖2所示，Online_Greedy算法是在一個充電周期T內，充電車從基站出發選擇距離基站服務時間最短的節點為第一個充電節點，隨后每一個納入充電路徑的節點都是距離當前充電節點服務時間最短的傳感器節點。

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

在WRSNs網絡中，假設充電車當前充電節點為vi，下一個充電節點為vj。我們用Qj表示節點vj的服務時間。節點vj的服務時間為單個傳感器充電時間C、從節點vi移動到節點vj的時間tij、從當前vj節點返回基站時間tj0三者時間之和, 即Qj=C+tij+tj0。用Wj表示節點vj的服務耗電量，節點vj的服務耗電量為單個傳感器充電的電量L、從節點vi移動到節點vj的耗電eij、從當前vj節點返回基站的移動耗電ej0三者時間之和，即Wj=L+eij+ej0。

圖2中實線箭頭區域表示充電車第一段充電路徑。充電車為下一個節點提供充電服務前，會計算自身剩余電量是否能夠為下一個節點充電以及支撐其返回基站。若電量充足，充電車繼續為傳感器節點充電，反之充電車就返回基站蓄電，然后進行下一輪的充電。圖2虛線箭頭部分表示充電車返回基站蓄電后再次出發的第二段充電路徑。表2為算法描述中符號和函數定義。

表2 算法符號和函數定義

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

算法1Online_Greedy算法

輸入:一個等待充電的傳感器集合Vc,充電周期T,充電周期總電量E輸出:始點為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算法

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

Online_MST_Cluster算法先對當前待充電的傳感器節點劃分聚類，再計算生成的子聚類中所有的傳感器節點實現全部充電所消耗的時間和電量，當充電的時間和電量消耗滿足限制條件時，充電車從基站出發為該聚類充電，充電完成后返回基站，在充電時間T內反復迭代上述過程。

Online_Greedy算法是對單個節點提供充電服務，而在Online_MST_Cluster算法中，充電車為聚類內包含的所有傳感器節點提供充電服務。Online_MST_Cluster算法的充電模型如圖3所示。

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

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

算法2Online_MST_Cluster算法

輸入:一個等待充電的傳感器集合Vc, 充電周期T, 充電周期總電量E, 常數K輸出:始點為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值從小到大進行排序?/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內，采用Online_MST_Cluster算法去解決最大充電傳感器數問題，該算法的時間復雜度為O(|V|2·lg|V|·T)，|V|是總傳感器數量。

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

3 實驗結果與分析

這一節將通過5組模擬實驗對比2個算法的性能，實驗的參數設置如表3所示。

表3 實驗參數設置

實驗是在固定范圍的監測區域內進行模擬對比實驗，基站位于監測區域內。實驗參數如表3所示，每一組實驗數據對應一幅實驗結果圖。由于不同傳感器作業任務不同，傳感器節點電量低于預定閾值Mi=α·Bi就向基站和充電車發送充電請求信號。

本文以一個充電周期T內被充電的傳感器數量的多少來衡量充電算法的性能。

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

Offline_Aglo是基于窮舉策略的離線精確算法。我們對比離線精確算法Offline_Aglo與兩個在線算法Online_Greedy、Online_MST_Cluster的執行效果。其中離線精確算法Offline_Aglo是基于靜態充電請求網絡，而兩個在線算法是基于動態充電請求網絡。靜態充電請求網絡是每一個充電周期的待充電傳感器節點都事先給定，充電車在執行充電任務的過程中接收到的新充電請求將作為下一個充電周期的待充電節點。離線精確算法Offline_Aglo給出當前靜態充電請求網絡的最優解。實驗設有傳感器節點數量為10～50，充電周期T=60 s，總電量E=100 q。

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

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

3.2 無線可充電傳感器網絡規模

這一小節對比Online_Greedy算法和Online_MST_Cluster算法在不同的無線可充電傳感網絡規模下充電周期內的最大充電傳感器數。充電周期T=2 500 s, 總電量E=1 500 q, 傳感器節點數300～750。

實驗結果如圖5(a)所示，從圖中可知Online_MST_Cluster算法充電周期內的充電傳感器數量一直明顯優于Online_SPT算法。當網絡中的傳感器節點數量在300到500時，Online_Greedy算法充電周期內所充電的傳感器數量波動較大，這是因為Online_Greedy選取的第一個充電節點會對后面的實驗結果產生較大的影響。Online_MST_Cluster算法執行效果增長穩定。隨著網絡中傳感器數量逐漸增大，Online_Greedy算法、Online_MST_Cluster算法實現充電的傳感器數量分別占總待充電傳感器數量67%、76%。

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

(b) T=3 000 s E=3 000 q圖5 網絡規模與最大充電傳感器數

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

3.3 總電量

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

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

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

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

4 結 語

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