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

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

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

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

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

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

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

2．1如何構造支配集

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

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

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

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

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

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

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

2．2支配集的分布式構造算法

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

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

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

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

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

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

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

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

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

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