張青

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

0 引言

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

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

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

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

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

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

2 問(wèn)題描述

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

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

3 算法描述

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

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

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

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

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

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

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

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

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

ratio=L

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

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

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

4 調(diào)度流程

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

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

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

Output:充電回路C及耗費(fèi)電量等

//每隔一段時(shí)間t進(jìn)行一次待充電傳感器節(jié)點(diǎn)V(t)的監(jiān)測(cè)

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

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

5 實(shí)驗(yàn)結(jié)果及分析

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

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

圖3 充電車行走距離

圖4 充電車耗費(fèi)電量

6 結(jié)語(yǔ)

本文提出了兩種在小規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中進(jìn)行傳感器節(jié)點(diǎn)的貪心選取的算法，并找到充電車的充電回路C，并通過(guò)模擬實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

參考文獻(xiàn)：

[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.