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

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

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

1 網(wǎng)絡模型與問題描述

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

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

我們提出一種分布式的支配集構造方法。支配集中節(jié)點的位置作為基站的檢查點?；驹诿總€檢查點處可以通過單跳通信獲取數(shù)據(jù)。使用旅行商問題的近似算法可以得出一條經過所有檢查點的移動路徑?；狙卮寺窂揭苿硬⑹占W(wǎng)絡中的所有節(jié)點上的數(shù)據(jù)。

2．1如何構造支配集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 各個角色之間的轉換關系

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