一種基于移動(dòng)基站的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法

無(wú)線傳感器網(wǎng)絡(luò)由大量的微型傳感器節(jié)點(diǎn)組成，已在多種監(jiān)測(cè)應(yīng)用中起到重要作用。在這些應(yīng)用中，傳感器節(jié)點(diǎn)通過(guò)多跳通信將感知數(shù)據(jù)傳輸?shù)交尽；就且粋€(gè)靜止節(jié)點(diǎn)，使用最短路徑路由或其他路由方式收取數(shù)據(jù)。因此靠近基站的節(jié)點(diǎn)需要比遠(yuǎn)離基站的點(diǎn)轉(zhuǎn)發(fā)更多的數(shù)據(jù)，從而導(dǎo)致更快地耗盡能量并導(dǎo)致網(wǎng)絡(luò)不再連通。這些節(jié)點(diǎn)通常被叫做“熱點(diǎn)”。“熱點(diǎn)”問(wèn)題是傳統(tǒng)的數(shù)據(jù)收集協(xié)議所無(wú)法解決的問(wèn)題。

最近幾年，有學(xué)者提出使用移動(dòng)性來(lái)解決上述問(wèn)題。提出的策略可分為兩類(lèi)。第一類(lèi)方法使用一個(gè)或數(shù)個(gè)移動(dòng)基站在網(wǎng)絡(luò)中隨機(jī)行走并收集數(shù)據(jù)。這類(lèi)方法進(jìn)行一次數(shù)據(jù)收集所耗費(fèi)的時(shí)間是無(wú)法預(yù)期的。另一類(lèi)方法試圖將移動(dòng)性和路由結(jié)合?；颈恢付ㄒ苿?dòng)軌跡和速度，從而使其位置可以被預(yù)測(cè)，同時(shí)依然通過(guò)多跳路由方式收集數(shù)據(jù)。這類(lèi)機(jī)制減少了數(shù)據(jù)延遲，但由于其較復(fù)雜，因而難以在實(shí)際應(yīng)用。此外，這些方法大多基于UDG(UIlit Disk Graph)模型，即節(jié)點(diǎn)僅能與在某個(gè)圓形區(qū)域內(nèi)的鄰居節(jié)點(diǎn)通信。該模型與現(xiàn)實(shí)差別較大，影響了這些方法的實(shí)用效果。本文提出一種使用移動(dòng)基站但不使用多跳路由機(jī)制的數(shù)據(jù)收集方法。其目標(biāo)是克服現(xiàn)有方法在復(fù)雜度和實(shí)用性上的不足，減少通信代價(jià)，并平衡各節(jié)點(diǎn)的能量消耗。

1 網(wǎng)絡(luò)模型與問(wèn)題描述

連通的，在圖G的定義外，存在一個(gè)移動(dòng)基站，用來(lái)收集y中所有節(jié)點(diǎn)的監(jiān)測(cè)數(shù)據(jù)。收集過(guò)程中不考慮數(shù)據(jù)聚合，并假定移動(dòng)基站與靜止節(jié)點(diǎn)具有相同的通信能力?；驹谝苿?dòng)過(guò)程中在支配集中各點(diǎn)的位置短暫停留，當(dāng)且僅當(dāng)其停留時(shí)與周?chē)o止的節(jié)點(diǎn)通信并收集數(shù)據(jù)。本文定義網(wǎng)絡(luò)壽命為從傳感器網(wǎng)絡(luò)部署成功到第一個(gè)傳感器節(jié)點(diǎn)因能量耗盡而停止工作的時(shí)間。傳感器消耗能量的活動(dòng)包括感知、計(jì)算、睡眠、等待、接收和發(fā)送數(shù)據(jù)，其中通信消耗的能量是最多的。本文的主要目的是最大化網(wǎng)絡(luò)壽命，近似等價(jià)于盡可能地減少通信代價(jià)并平衡負(fù)載分布。

2 基于移動(dòng)基站的數(shù)據(jù)收集

我們提出一種分布式的支配集構(gòu)造方法。支配集中節(jié)點(diǎn)的位置作為基站的檢查點(diǎn)。基站在每個(gè)檢查點(diǎn)處可以通過(guò)單跳通信獲取數(shù)據(jù)。使用旅行商問(wèn)題的近似算法可以得出一條經(jīng)過(guò)所有檢查點(diǎn)的移動(dòng)路徑?；狙卮寺窂揭苿?dòng)并收集網(wǎng)絡(luò)中的所有節(jié)點(diǎn)上的數(shù)據(jù)。

2．1如何構(gòu)造支配集

對(duì)于給定的圖C，其支配集不是唯一的。各個(gè)支配集的勢(shì)也不一定相等。支配集的勢(shì)|s|越小，基站所必須停留的位置越少，在轉(zhuǎn)化為旅行商問(wèn)題求解時(shí)的約束條件就越少。直觀上認(rèn)為，約束條件較少時(shí)可能獲得更優(yōu)的解。因此，我們需要構(gòu)造一個(gè)具有較小勢(shì)的支配集。已有的研究主要聚焦于連通支配集的構(gòu)造，而本文僅需非連通的支配集。最小支配集求解問(wèn)題已被證明是“NP-完全”問(wèn)題，在傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)解決該問(wèn)題的算法可能帶來(lái)非常大的能量消耗，甚至可能遠(yuǎn)遠(yuǎn)超出其較少的勢(shì)帶來(lái)的收益。因此，我們提出一種分布式啟發(fā)式算法，在構(gòu)造具有較小勢(shì)的支配集的同時(shí)降低了單個(gè)節(jié)點(diǎn)的通信消耗，并且使各個(gè)節(jié)點(diǎn)的通信消耗趨于均衡。該算法主要遵循以下兩條規(guī)則：

規(guī)則1 在任意一條路徑上，盡量每隔兩個(gè)節(jié)點(diǎn)選一個(gè)節(jié)點(diǎn)作為支配點(diǎn)。

在強(qiáng)連通的圖中，從任意一點(diǎn)出發(fā)，必然有到達(dá)任意其他點(diǎn)的最短路徑。令n表示路徑中所包含點(diǎn)的個(gè)數(shù)，對(duì)于一條足夠長(zhǎng)的路徑(n≥3)，一定包括由三個(gè)連續(xù)節(jié)點(diǎn)組成的單元。只要將處于中間的節(jié)點(diǎn)添加進(jìn)支配集，就能保證每個(gè)節(jié)點(diǎn)都被中間的節(jié)點(diǎn)支配。路徑長(zhǎng)度n按照nmod3的結(jié)果可以分為三類(lèi)，即

當(dāng)n=3m時(shí)，按照?qǐng)D中的方式選擇節(jié)點(diǎn)構(gòu)造支配集；當(dāng)n=3m-1或n=3m-2時(shí)，在路徑的前3(m—1)個(gè)節(jié)點(diǎn)部分采用圖1所示方式選擇節(jié)點(diǎn)，然后再加上路徑中的最后一個(gè)節(jié)點(diǎn)構(gòu)成支配集。該結(jié)論的證明可參考圖論中關(guān)于環(huán)中最小支配集的勢(shì)的定理相關(guān)證明，因篇幅限制，此處略過(guò)相關(guān)證明。

圖1一條路徑上的最小支配集

規(guī)則2盡可能選擇度數(shù)高的節(jié)點(diǎn)作為支配集中節(jié)點(diǎn)。

由于圖中含有多條相交的路徑，因此僅使用上述規(guī)則并不能保證結(jié)果最優(yōu)。當(dāng)分布式實(shí)現(xiàn)上述規(guī)則時(shí)，尤其是網(wǎng)絡(luò)中節(jié)點(diǎn)密度比較大的前提下，經(jīng)常出現(xiàn)兩個(gè)或多個(gè)相鄰節(jié)點(diǎn)同時(shí)在不同的路徑中被選擇作為支配集中節(jié)點(diǎn)的情況，從而導(dǎo)致最終生成的支配集中存在多個(gè)相鄰節(jié)點(diǎn)。直觀地認(rèn)為，在多個(gè)相鄰節(jié)點(diǎn)競(jìng)爭(zhēng)時(shí)，應(yīng)當(dāng)采用貪婪的方式，選擇具有較高度數(shù)的節(jié)點(diǎn)加入到支配集中。

2．2支配集的分布式構(gòu)造算法

分布式算法不需要中心化的管理，并且當(dāng)問(wèn)題規(guī)模變得很大時(shí)集中式算法的代價(jià)也難以接受。為了分布式地實(shí)現(xiàn)前文所描述的啟發(fā)式算法規(guī)則，我們使用不同的角色來(lái)標(biāo)志節(jié)點(diǎn)當(dāng)前在支配集構(gòu)造過(guò)程中的狀態(tài)。定義節(jié)點(diǎn)角色可能的取值如下：

·NULL：表示初始化狀態(tài)，節(jié)點(diǎn)還沒(méi)被賦予任何角色；

·DOMINATOR：表示是支配集中的節(jié)點(diǎn)；

·DOMINATEE：表示是被支配集中某個(gè)節(jié)點(diǎn)支配的節(jié)點(diǎn)；

·2-NEIGHBOR：表示是支配集中某個(gè)節(jié)點(diǎn)的第二跳鄰居，即某個(gè)被支配節(jié)點(diǎn)的鄰居；

·CANDIDATE：表示是支配集中節(jié)點(diǎn)的候選節(jié)點(diǎn)。

算法開(kāi)始時(shí)，任意選擇網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，將其角色設(shè)置為DOMINATOR，并將該角色狀態(tài)以廣播的方式告知其鄰居節(jié)點(diǎn)。這些鄰居節(jié)點(diǎn)收到該廣播消息后，將自己的角色設(shè)置為烈刪TEE，并將新的角色進(jìn)行廣播。每個(gè)節(jié)點(diǎn)收到不同類(lèi)型的角色消息后按不同方式處理，并用廣播發(fā)送自己的角色信息。依此擴(kuò)展開(kāi)去，最終引起全網(wǎng)范圍內(nèi)所有節(jié)點(diǎn)至少?gòu)V播一次。當(dāng)所有節(jié)點(diǎn)的角色都是DOMINATOR或DOMINATEE時(shí)，節(jié)點(diǎn)不會(huì)再改變角色，也不會(huì)再?gòu)V播新的消息，算法終止。此時(shí)，所有角色為DOMINATOR的節(jié)點(diǎn)就構(gòu)成一個(gè)支配集。

各個(gè)角色之間的轉(zhuǎn)換關(guān)系如圖2所示。其中，收到角色狀態(tài)消息后的狀態(tài)變化遵循第一條規(guī)則。為了實(shí)現(xiàn)第二條規(guī)則，當(dāng)節(jié)點(diǎn)角色變?yōu)镃ANDIDATE后，將會(huì)建立一個(gè)定時(shí)器，在一段時(shí)間延遲后觸發(fā)。若在定時(shí)器觸發(fā)之前，該節(jié)點(diǎn)收到DOMINATOR狀態(tài)消息，則將自己的角色設(shè)置為DOMINATEE并取消定時(shí)器。若定時(shí)器被觸發(fā)，則將節(jié)點(diǎn)角色設(shè)置為DOMINATOR。令節(jié)點(diǎn)秒上定時(shí)器時(shí)間延遲的長(zhǎng)度為t(v)=C／|N(v)|，其中C為正的常數(shù)。這樣，在兩個(gè)相鄰的CANDIDATE節(jié)點(diǎn)同時(shí)建立定時(shí)器后，擁有更高度數(shù)的節(jié)點(diǎn)將先觸發(fā)定時(shí)器并成為DOMINATOR，另一節(jié)點(diǎn)在收到廣播消息后則會(huì)成為烈)肘刀vATEE。但僅按上文描述的方式進(jìn)行角色轉(zhuǎn)換，并不能保證在所有節(jié)點(diǎn)廣播一次后全網(wǎng)節(jié)點(diǎn)的狀態(tài)都是DOMINATOR或DOMINATEE，還可能存在角色為2-NEIGHBOR。這些節(jié)點(diǎn)都正好處于規(guī)則l中所述某條從最初選擇的DOMINATOR節(jié)點(diǎn)出發(fā)的最短路徑的末端，但這些節(jié)點(diǎn)的相鄰關(guān)系無(wú)法判定。因此，每個(gè)節(jié)點(diǎn)需要記錄每個(gè)鄰居是否廣播過(guò)消息，如果是，則建立一個(gè)時(shí)長(zhǎng)隨機(jī)的定時(shí)器。定時(shí)器觸發(fā)后則將該節(jié)點(diǎn)角色設(shè)置為DOMINATOR并

圖2 各個(gè)角色之間的轉(zhuǎn)換關(guān)系

下面以圖3為例來(lái)說(shuō)明算法構(gòu)造支配集的過(guò)程。圖3(a)中是一個(gè)簡(jiǎn)單的網(wǎng)絡(luò)，我們選擇節(jié)點(diǎn)1作為起始節(jié)點(diǎn)，將其角色設(shè)置為DOMINATOR，然后廣播消息；節(jié)點(diǎn)2和3收到后，其角色變?yōu)镈OMINATEE，然后分別廣播消息；按照前文所述規(guī)則，節(jié)點(diǎn)4—9的角色都將轉(zhuǎn)換為2一NEICHBOR，并各自廣播消息。圖3(b)中，節(jié)點(diǎn)10和11分別收到節(jié)點(diǎn)6和7的廣播消息后，角色變?yōu)镃ANDIDATE，并根據(jù)節(jié)點(diǎn)的度建立定時(shí)器；同時(shí)，節(jié)點(diǎn)4、5和9發(fā)現(xiàn)所有鄰居節(jié)點(diǎn)都已發(fā)送過(guò)消息，也各自建立定時(shí)器；節(jié)點(diǎn)5的定時(shí)器先觸發(fā)(或節(jié)點(diǎn)4的定時(shí)器先觸發(fā))，則將其角色轉(zhuǎn)換為DOMINATOR，并廣播消息，節(jié)點(diǎn)4收到后將角色轉(zhuǎn)換為DOMINATEE；而節(jié)點(diǎn)9在定時(shí)器觸發(fā)后也將角色轉(zhuǎn)換為DOMINATOR。圖3(e)中，節(jié)點(diǎn)11的定時(shí)器先觸發(fā)，隨后節(jié)點(diǎn)10成為DOMINATEE，并廣播消息。在圖3(d)中，節(jié)點(diǎn)6收到節(jié)點(diǎn)10的消息后，發(fā)現(xiàn)所有鄰居都已廣播過(guò)消息，建立定時(shí)器。并最終也成為DOMINATOR。此時(shí)，節(jié)點(diǎn)6發(fā)送廣播消息已經(jīng)不會(huì)再觸發(fā)新的廣播消息，支配集生成完畢。