小規模無線傳感器網絡的充電節點選取貪心策略

張青

（四川大學計算機學院，成都 610065）

0 引言

如今無線傳感器網絡應用于諸多領域，工業控制、智能家居、軍事監測、惡劣環境監控以及健康監測等諸多領域，為大眾提供了一種快捷而精確的監控環境。無線傳感器網絡是一種分布式的傳感網絡，通過部署的傳感器節點感知外部的參數變化，節點之間以無線方式進行通信，同時還與互聯網進行有線或無線方式的連接，從而形成了一個多跳自組織的網絡。無線傳感器網絡的部署具有較高的可靠性、易于擴展、價格實惠等特點。縱觀現有的無線傳感器網絡的應用，可以粗略劃分為大規模無線傳感器網絡和小規模無線傳感器網絡兩種。

在大規模無線傳感器網絡中，需要部署大量的無線傳感器節點來監測很大的地理空間，因此，需要充電的無線傳感器節點也較多，充電車數量也相應會增加。大規模無線傳感器網絡的充電調度變得更為復雜。本文針對大規模無線傳感器網絡的特點，考慮到大規模無線傳感器網絡通常會由區域劃分的方式轉化為小規模無線傳感器網絡，因此，本文著重考慮小規模無線傳感器網絡。本文將提出兩種效率較為高效的節點選取貪心算法。

1 網絡模型

出于對小規模無線傳感器網絡的考慮，本文從一個部署了30個傳感器節點的無線傳感器網絡著手分析。假設該30個無線傳感器節點隨機部署在一個50m×50m的二維平面空間上，同時，為了保證傳感器數據可以被較為便捷地傳遞到基站，本文考慮將基站部署在二維平面空間的中間位置。

圖1為無線傳感器網絡圖，通常，當一個傳感器節點的剩余生命時間到了一定的閾值，例如，剩余電池容量的10%，該傳感器節點便被稱為待充電傳感器節點。

為了便于對無線傳感器網絡進行研究，本文構建一個網絡圖G=( )V,E,h,l，其中，V是n個待充電傳感器節點集合，E是待充電傳感器節點的所有邊，h(v)表示待充電傳感器節點v需要被充的電量，l(u,v)表示待充電傳感器節點u和v之間的歐幾里得距離。

2 問題描述

本文研究的問題是基于小規模無線傳感器網絡中充電傳感器節點的選取問題，并找到充電車的充電回路C。

為了提高傳感器網絡的充電效率，盡可能地充分利用充電車的電池電量，盡量減少網絡中因能量耗盡而死亡的傳感器節點，需要綜合考慮傳感器充電緊迫性、充電車在充電回路的行走距離L以及為充電車所充電量Q這三個因素。針對是否考慮傳感器節點充電緊迫性這個因素，本文分別提出兩個算法。

3 算法描述

傳感器節點能力耗盡的話，將會無法工作，從而導致無法上傳感應和傳遞信息。如上節所述，鑒于本文研究的是小規模無線傳感器網絡中傳感器節點充電選取問題，因此，可以假定一輛充電車便可以滿足一趟充電回路的需求。

為了充分考慮待充電傳感器節點的剩余生命時間T和充電車的行走距離L，保證盡可能多的傳感器節點處于工作狀態。

如圖2所示，本文考慮采用貪心算法來求該問題的最優解。假設在時刻t的待充電傳感器節點為V(t)。

算法一考慮了傳感器節點充電緊迫性這個因素，其參數模型為：

sum(Q)為充電車為待充電傳感器節點所充的電量之和，即：

而sum(L)為充電車在行走途中的行走距離之和，

當充電回路C從0個節點開始，遍歷未充電的傳感器節點，找到使：

最大的節點v，加入充電回路C。

算法二則考慮充電車的行走距離L這個因素，

ratio=L

每次將加入距離上一次加入C中傳感器最近的其他傳感器節點加入充電回路C。

圖1 無線傳感器網絡圖

圖2 充電車回路C節點選取

4 調度流程

兩個調度算法的偽代碼如下：

算法一基于緊迫性的充電節點選取貪心算法Sensor Selection Greedy Algorithm based on Urgence(SSGAU)

Input:網絡模型G=(V ,E,h,l)

Output:充電回路C及耗費電量等

//每隔一段時間t進行一次待充電傳感器節點V(t)的監測

算法二基于鄰近算法的充電節點選取貪心算法Nearest Neighbor Sensor Selection Greedy Algorithm(NNSSGA)

算法一的主要過程在于遍歷V(t)的過程中，實現貪心算法，即，找到ratio值最大的節點v作為下一個被充電的傳感器節點，而算法二則是距離最鄰近算法的擴展。

5 實驗結果及分析

下面，本文采用仿真模擬實驗進行驗證。30個無線傳感器節點隨機部署在一個50m×50m的二維平面空間上，其他實驗環境參數參考文獻[1,2,3]中的隨機模擬環境。

如圖3和圖4所示，在相同的實驗環境中，對比本文提出的SSGAU算法、NNSSGA算法以及未采用調度算法的情況下的算法NONE、SSGAU算法和NNSSGA算法在充電車行走距離和充電回路耗費電量上均比算法NONE小。因此，本文所提出的這兩種算法在充電傳感器節點的選取問題上，效率更高。

圖3 充電車行走距離

圖4 充電車耗費電量

6 結語

本文提出了兩種在小規模無線傳感器網絡中進行傳感器節點的貪心選取的算法，并找到充電車的充電回路C，并通過模擬實驗驗證了該算法的有效性。

參考文獻：

[1]W.Liang,W.Xu,X.Ren,X.Jia，X.Lin.Maintaining large-Scale Rechargeable Sensor Networks Perpetually Via Multiple Mobile Charging Vehicles[J].ACM Trans.Sensor Netw.(TOSN),vol.12,no.2,article no.14,May.2016.

[2]A.Kurs,A.Karalis,R.Moatt,J.D.Joannopoulos,P.Fisher，M.Soljacic.Wireless Power Transfer Via Strongly Coupled Magnetic Resonances[J].Sci.,vol.317,no.5834：83-86,Jul.2007

[3]Y.Shi,L.Xie,Y.T.Hou，H.D.Sherali.On Renewable Sensor Networks with Wireless Energy Transfer[M].in Proc.30th IEEE Int.Conf.Comput.Comm.(INFOCOM),2011：1350-1358.