小規(guī)模無線傳感器網(wǎng)絡(luò)的充電節(jié)點選取貪心策略

張青

（四川大學(xué)計算機學(xué)院，成都 610065）

0 引言

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

在大規(guī)模無線傳感器網(wǎng)絡(luò)中，需要部署大量的無線傳感器節(jié)點來監(jiān)測很大的地理空間，因此，需要充電的無線傳感器節(jié)點也較多，充電車數(shù)量也相應(yīng)會增加。大規(guī)模無線傳感器網(wǎng)絡(luò)的充電調(diào)度變得更為復(fù)雜。本文針對大規(guī)模無線傳感器網(wǎng)絡(luò)的特點，考慮到大規(guī)模無線傳感器網(wǎng)絡(luò)通常會由區(qū)域劃分的方式轉(zhuǎn)化為小規(guī)模無線傳感器網(wǎng)絡(luò)，因此，本文著重考慮小規(guī)模無線傳感器網(wǎng)絡(luò)。本文將提出兩種效率較為高效的節(jié)點選取貪心算法。

1 網(wǎng)絡(luò)模型

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

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

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

2 問題描述

本文研究的問題是基于小規(guī)模無線傳感器網(wǎng)絡(luò)中充電傳感器節(jié)點的選取問題，并找到充電車的充電回路C。

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

3 算法描述

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

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

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

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

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

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

當(dāng)充電回路C從0個節(jié)點開始，遍歷未充電的傳感器節(jié)點，找到使：

最大的節(jié)點v，加入充電回路C。

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

ratio=L

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

圖1 無線傳感器網(wǎng)絡(luò)圖

圖2 充電車回路C節(jié)點選取

4 調(diào)度流程

兩個調(diào)度算法的偽代碼如下：

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

Input:網(wǎng)絡(luò)模型G=(V ,E,h,l)

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

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

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

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

5 實驗結(jié)果及分析

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

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

圖3 充電車行走距離

圖4 充電車耗費電量

6 結(jié)語

本文提出了兩種在小規(guī)模無線傳感器網(wǎng)絡(luò)中進行傳感器節(jié)點的貪心選取的算法，并找到充電車的充電回路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.