匡哲君，師唯佳，胡 亮，周 航

（1.吉林大學 計算機科學與技術(shù)學院，長春130012；2.羅格斯新澤西州立大學 教育研究與學術(shù)規(guī)劃處，新布倫斯威克 新澤西州 美國08901；3.吉林大學 數(shù)學學院，長春130012）

0 引 言

無線傳感器網(wǎng)絡的生命周期的定義很多，通常認為無線傳感器網(wǎng)絡的生命周期是從正常工作到出現(xiàn)一個傳感器節(jié)點能量耗盡為止為一個無線傳感器網(wǎng)絡的生命周期。在傳感器節(jié)點通信的過程中，一般由多個節(jié)點進行數(shù)據(jù)的收集，然后由底向上進行數(shù)據(jù)的匯聚。也就是說，數(shù)據(jù)收集后的多個節(jié)點向一個或者少部分的匯聚節(jié)點發(fā)送數(shù)據(jù)。根據(jù)多跳路由的機制，一般由邊緣節(jié)點進行數(shù)據(jù)的收集，然后由匯聚節(jié)點附近的節(jié)點進行轉(zhuǎn)發(fā)。在這種過程中容易出現(xiàn)“中心擁擠效應”［1］，也就是通常所說的“能量洞”問題［2］。這種問題是由于匯聚節(jié)點附近的鄰節(jié)點能提前耗盡，使得邊緣節(jié)點還有能量卻無法將數(shù)據(jù)發(fā)送至匯聚節(jié)點。文獻［3］提出了移動代理的機制，移動代理節(jié)點代替靜態(tài)的匯聚節(jié)點能夠移動到節(jié)點附近進行數(shù)據(jù)的收發(fā)。當移動到匯聚節(jié)點附近再將接受到的數(shù)據(jù)發(fā)送到匯聚節(jié)點。在這個結(jié)構(gòu)下，節(jié)點只需要與移動代理節(jié)點進行單跳的數(shù)據(jù)傳輸，而移動代理節(jié)點對匯聚節(jié)點也同樣是單跳進行數(shù)據(jù)的傳輸。這樣就減輕了節(jié)點由于作為中繼節(jié)點所消耗的能量。這種結(jié)構(gòu)是在移動代理節(jié)點的能量非常大的假設條件下進行的。文獻［4］論證了移動代理的移動規(guī)律，通過移動規(guī)律和停留時長來延長整個網(wǎng)絡的生命周期，其框架應用的網(wǎng)絡拓撲結(jié)構(gòu)以網(wǎng)格模式進行考慮，過于單一。文獻［5］表明，移動節(jié)點的消耗取決于匯聚節(jié)點移動的范圍和匯聚節(jié)點最短的停留時間，并且當移動節(jié)點移動到下一站時，模型定義了跳寬；同時，作者提出了一種MILP的方法來取得移動匯聚節(jié)點的最優(yōu)移動路徑和最適合的停留時間來保證網(wǎng)絡生命周期。文獻［6］表明，移動代理在邊緣點附近移動可以提高整體網(wǎng)絡的生命周期，文中假設如果移動代理節(jié)點能夠調(diào)整整體網(wǎng)絡節(jié)點的負載平衡，這樣可以提高整體網(wǎng)絡生命周期；作者以負載中的節(jié)點作為移動節(jié)點，降低惡劣節(jié)點負載不平衡的問題。由于假設環(huán)境是在最短路徑下進行的，網(wǎng)絡生命周期提升的效果并不明顯。隨著移動匯聚節(jié)點的產(chǎn)生，在不考慮監(jiān)測環(huán)境的空間復雜度和節(jié)點停留的基礎上，很難進行移動路徑的規(guī)劃。文獻［7］研究了如何找出移動路徑的最短停留時間和停留時間表。如果監(jiān)測區(qū)的停留時間不受到約束，就會成為一個NP 問題。然而停留在一個有限的已知區(qū)域，這樣問題就可以轉(zhuǎn)化成為一種線型。作者提出一種接近算法，將監(jiān)測區(qū)看作無限的未知區(qū)域。這樣就能將無限的問題轉(zhuǎn)化為有限的問題，然而一個好的逼近問題需要消耗大量的計算資源及能耗。文獻［8－10］在節(jié)點功耗管理方面提出了優(yōu)化的策略。文獻［11］提出了一種分簇式自主移動機制，該機制設定匯聚節(jié)點單跳鄰居節(jié)點集的數(shù)據(jù)流量發(fā)生較大變化時，匯聚節(jié)點開始移動。文獻［12］根據(jù)移動的特性，即移動節(jié)點只能在若干個小的區(qū)域內(nèi)移動，得出網(wǎng)絡生命周期的延長不僅依賴于停留時長，還需要考慮流量。

本文通過應用層對數(shù)據(jù)傳輸?shù)难舆t容忍級別，利用移動匯聚節(jié)點，進行周期性的數(shù)據(jù)收集。移動匯聚節(jié)點延遲容忍策略能夠緩解網(wǎng)絡中的“能量洞”問題，并且在延遲容忍的基礎上，能夠很大程度上降低數(shù)據(jù)傳輸?shù)哪芎模_到延長網(wǎng)絡生命周期的效果。

1 匯聚節(jié)點能耗模型

1.1 靜態(tài)匯聚節(jié)點

對無線傳感器網(wǎng)絡能耗進行分析，首先需要了解靜態(tài)匯聚節(jié)點下的能量消耗與數(shù)據(jù)傳輸?shù)年P系。設傳感器節(jié)點集合為N。假設所有的傳感器節(jié)點都是隨機散落在以R 為半徑的圓形區(qū)域內(nèi)。以圓形區(qū)域的中心作為起點，每個節(jié)點i以固定比例生成數(shù)據(jù)di且i的初始能量為Ei。此外，節(jié)點能夠根據(jù)傳輸距離來調(diào)整傳輸功率。節(jié)點i向j發(fā)送固定比例的通信量速率Xij，在一個單位時間內(nèi)所需要的能量可以表示為：

式中：dis（i，j）為節(jié)點i與j的歐幾里得距離；α和β為非負數(shù)常量；e為路徑的損耗指數(shù)，一般來說，e的范圍為2～6，e值的選取主要取決于監(jiān)測的環(huán)境。

單位數(shù)據(jù)的傳輸能耗不依賴于鏈路速率，而是取決于有效的低速率機制。因此，假設相比于無線鏈路速率，通信量速率Xij足夠小。節(jié)點i單位時間內(nèi)接收到節(jié)點k 發(fā)送的數(shù)據(jù)能耗可以表示為：

式中：γ為給定的一個常量。

節(jié)點i在一個單位時間內(nèi)總的能耗可以表示為：

1.2 移動匯聚節(jié)點

在移動匯聚節(jié)點模型中，假設匯聚節(jié)點可以在傳感器監(jiān)測區(qū)域進行移動，并且可以在特定的區(qū)域進行停留來與傳感器節(jié)點進行數(shù)據(jù)的收發(fā)。假設每一個節(jié)點都有相同的傳輸范圍，I 表示為匯聚節(jié)點。在本文中，設移動匯聚節(jié)點I屬于一個特殊的節(jié)點（不同于其他節(jié)點），可以表示為I ?N。設L 為匯聚節(jié)點停留的位置節(jié)點集合。為了提高網(wǎng)絡生命周期，匯聚節(jié)點沒有必要在所有的L位置上進行停留。假設在不考慮匯聚節(jié)點移動時間的條件下，為簡化問題，可以通過明確的數(shù)學解法來進行評估。

在此模型中，節(jié)點的訪問順序?qū)W(wǎng)絡的整體生命周期并不會帶來太大的影響。匯聚節(jié)點在一個位置I∈L 的停留時間可以表示為ZI，也就是說匯聚節(jié)點使用I時間對傳感器節(jié)點進行數(shù)據(jù)的收發(fā)。因此，整體的生命周期為當匯聚節(jié)點停于I 位置，節(jié)點i的下游鄰節(jié)點可表示為：

移動匯聚節(jié)點的停留時間需要根據(jù)流量來制定。根據(jù)之前靜態(tài)匯聚節(jié)點延長網(wǎng)絡生命周期的基本感知數(shù)據(jù)流量的聚合和靜態(tài)匯聚節(jié)點數(shù)據(jù)聚合的基本理論，將移動匯聚節(jié)點的條件進行迭代。用X（I）ij表示移動匯聚節(jié)點在I 站點停留時節(jié)點i到j 的數(shù)據(jù)流聚合。最大網(wǎng)絡生命周期可以表示為：

式（7）表示所有的匯聚節(jié)點在i位置是流量守恒的。式（8）表明所有的節(jié)點i的能耗必須少于或等于初始能量Ei，即能量是守恒的。通過將式（7）乘以ZI，并且用新的參數(shù)替換，有：

同理，式（8）可轉(zhuǎn)換為：

2 移動匯聚節(jié)點延遲容忍策略

無線傳感器網(wǎng)絡生命周期最大化是建立在應用層面的延遲容忍條件基礎上的。一般將這種模型稱之為延遲容忍模型。假設每一個節(jié)點能夠延遲到移動匯聚節(jié)點停留在最有利的位置之后再進行數(shù)據(jù)的收發(fā)，這樣使得收發(fā)同樣數(shù)據(jù)量時能耗達到最小，從而延長了整個網(wǎng)絡的生命周期。

設D 為最大延遲容忍，或者是最高延遲級別。假設在D 個單位時間內(nèi)移動匯聚節(jié)點能夠完成所有停留節(jié)點的一輪訪問，并且在適當?shù)恼军c進行數(shù)據(jù)收集，以此為周期進行重復。

延遲容忍模型相比于靜態(tài)匯聚節(jié)點模型和移動匯聚節(jié)點模型在延長網(wǎng)絡生命周期方面有明顯的優(yōu)勢。如圖1所示，N1和N2為兩個傳感器節(jié)點，L1和L2為移動匯聚節(jié)點的備用站點。為了簡化說明，忽略節(jié)點收發(fā)的能量消耗，并且假設一個單位量的數(shù)據(jù)傳輸耗能為收發(fā)節(jié)點之間距離的平方。在初始環(huán)境下，兩個節(jié)點的初始能量都為100單位量，初始基本感知數(shù)據(jù)為1bit／s。如果在靜態(tài)匯聚節(jié)點模式下，匯聚節(jié)點將處于O 位置并保持不變。那么1bit的數(shù)據(jù)傳輸能耗約為4個單位量。也就是說從開始到節(jié)點衰竭，其網(wǎng)絡周期約為25s。同樣的環(huán)境，在動態(tài)匯聚節(jié)點模式下，由于是對稱的結(jié)構(gòu)，移動節(jié)點會周期性地停留在L1和L2進行數(shù)據(jù)傳輸。這種情況之下，每一個節(jié)點都需要消耗1個單位或者9個單位能量來傳輸1bit的數(shù)據(jù)量。無論移動匯聚節(jié)點停留在L1還是L2。也就是說平均能耗約為5個單位量，其網(wǎng)絡生命周期約為20s。

圖1 靜態(tài)節(jié)點與移動匯聚點的假設Fig.1 Assuming static and mobile sink node

在延遲移動匯聚節(jié)點模式下，假設移動匯聚節(jié)點在每一個站點都停留1s的時間，且周期性地重復。在此情況下，最大延遲D＝2s。當移動匯聚節(jié)點停留在L1位置時，只有N1與匯聚節(jié)點進行數(shù)據(jù)傳輸，并傳輸2bit的數(shù)據(jù)。當移動匯聚節(jié)點停留至L2位置時，只有N2與匯聚節(jié)點進行數(shù)據(jù)傳輸通信，同樣傳輸2bit的數(shù)據(jù)。也就是說，當移動匯聚節(jié)點與N1在L1位置上進行數(shù)據(jù)傳輸時，N2只是進行數(shù)據(jù)的采集并將數(shù)據(jù)放入緩沖池，等到移動匯聚節(jié)點移動至L2時，再將采集來的所有數(shù)據(jù)發(fā)送給匯聚節(jié)點。如此一來，每一個節(jié)點只需要使用2個單位能量就能傳輸2bit的數(shù)據(jù)，其生命周期約為100s。相比于靜態(tài)匯聚節(jié)點和移動匯聚節(jié)點模型，網(wǎng)絡的生命周期延長非常顯著。這是因為節(jié)點并不是需要持續(xù)地與匯聚節(jié)點進行通信的。在移動匯聚節(jié)點停留時，每一個節(jié)點都需要等待匯聚節(jié)點移動至最有利的位置才進行數(shù)據(jù)的傳輸。

延遲容忍模型中，可以通過局部子區(qū)域的方式對所有節(jié)點進行數(shù)據(jù)收集。設N 為傳感器節(jié)點集合，RI為N 的子集并且只有RI區(qū)域的節(jié)點與停留在I 站點的匯聚節(jié)點進行數(shù)據(jù)交換，I ∈L?？梢詫I稱為站點I 的覆蓋區(qū)域。所有I站點RI的集合應該為N。也就是說，所有傳感器節(jié)點都至少能夠有一個站點與其進行通信。當節(jié)點i在RI的范圍內(nèi)，則節(jié)點i就是站點i的區(qū)域節(jié)點（I∈L）。設r為匯聚節(jié)點的適合通信半徑。對所有的I屬于L 來說，如果dis（i，l）≤r且i∈N，則i∈RI。因此，匯聚節(jié)點的通信半徑必須足夠大，保證至少有一個節(jié)點在RI的范圍內(nèi)。r半徑的最小值取決于移動匯聚節(jié)點停留的位置。

節(jié)點i基本感知數(shù)據(jù)的生成和數(shù)據(jù)的傳輸速率在靜態(tài)匯聚節(jié)點和動態(tài)匯聚節(jié)點模式下是一樣的，不會產(chǎn)生數(shù)據(jù)的堆積。然而在延遲容忍模型中，數(shù)據(jù)收集的速率與出具傳輸?shù)乃俾什灰粯?。當移動匯聚節(jié)點沒有移動到合適節(jié)點i的傳輸站點，節(jié)點i不進行數(shù)據(jù)的傳輸，卻需要將收集來的數(shù)據(jù)存儲至緩沖區(qū)，在周期性產(chǎn)生基本感知數(shù)據(jù)的同時，等待匯聚節(jié)點移動到合適的站點，然后將新舊數(shù)據(jù)一起傳輸給匯聚節(jié)點。因此，節(jié)點i的緩沖區(qū)空間應該為Ddi。假設移動匯聚節(jié)點按一定順序訪問所有L里的站點1→2→3→…→｜L｜→1…。根據(jù)流量移動匯聚節(jié)點可能在某些站點不停留，如果網(wǎng)絡的生命周期為T，那么實際移動節(jié)點工作的時間為TD。緩沖區(qū)能夠有效地幫助延遲容忍模型來延長網(wǎng)絡的生命周期，但是需要根據(jù)應用環(huán)境的需求來制定不同的緩沖策略。

2.1 子流模式

在此模型中，覆蓋區(qū)域RI的節(jié)點不需要緩存其他節(jié)點的轉(zhuǎn)發(fā)信息，節(jié)點在RI區(qū)域接收到其他節(jié)點的數(shù)據(jù)后，將立即發(fā)送給相鄰節(jié)點。在這種模式條件下的每一個節(jié)點i需要區(qū)分節(jié)點i 自身生成的數(shù)據(jù)和節(jié)點接收到其他相鄰節(jié)點初始生成的數(shù)據(jù)。

節(jié)點i∈N，基本感知數(shù)據(jù)或子流量的其他節(jié)點C ∈RI，C ≠i，則必須接收后盡快地轉(zhuǎn)發(fā)出去，可以得到：

在此，定義NI（i）＝R∩N（i，I）。在式（5）里給出了N（i，I）。與移動匯聚節(jié)點模式的理論一樣，通信流量起源于節(jié)點i本身，并且加入了新的決策變量；I∈L，i∈RI），節(jié)點i的數(shù)據(jù)流量守恒可以表示為：

在移動匯聚節(jié)點前一次離開后，在緩沖區(qū)產(chǎn)生的數(shù)據(jù)流量需要在當前周期被傳輸給匯聚節(jié)點，并清空緩沖區(qū)。可表示為：

基于子流模式的延遲容忍可表示為：

上述是根據(jù)周期性產(chǎn)生節(jié)點的基本感知數(shù)據(jù)來進行解決的，與靜態(tài)匯聚節(jié)點模型問題相似，還有一種更為簡單、類似的流量聚合方案，它僅限于聚合擁堵數(shù)據(jù)量I。相 反 地，對 于聚合 方 案 的 可 行 性 解，可 以 將看作匯聚節(jié)點停留在I時對每個節(jié)點i的支持度。每一個節(jié)點i可以分解由基本感知產(chǎn)生的擁堵數(shù)據(jù)量，其路徑流量為。因此，為可行性解。

2.2 隊列模式

在隊列模式中，傳感器節(jié)點能夠緩存其他節(jié)點產(chǎn)生的數(shù)據(jù)，設移動匯聚節(jié)點從I位置移動到I＋1之前，節(jié)點i的隊列長度為。假設每個節(jié)點i在周期開始時的數(shù)據(jù)量為Ddi，并且隊列為當匯聚節(jié)點完成一個循環(huán)，節(jié)點i的隊列數(shù)據(jù)必須清空，即。在此模式下，根據(jù)流量守恒其動態(tài)的序列長度公式為：能量約束與之前的模式相同，可以通過將代入，并引入新的變量u＝1／T，將優(yōu)化問題轉(zhuǎn)化成為一個線性問題。這種線性方法也同樣適用于子流模式。

這兩種模式以公式化的形式表示了緩沖區(qū)的兩種策略。子流模式緩沖區(qū)存儲的是節(jié)點自身產(chǎn)生的數(shù)據(jù)，而隊列模式的緩沖區(qū)允許存儲任何數(shù)據(jù)，隊列模式能夠根據(jù)不同的策略來調(diào)整，達到延長生命周期的效果。兩種模式可以看作是兩種極端，可以根據(jù)實際情況進行調(diào)整緩沖區(qū)策略。在子流模式中最大空間區(qū)為節(jié)點i的Ddi。而隊列模型中的最大緩沖區(qū)空間由覆蓋區(qū)域的總節(jié)點數(shù)和覆蓋面積來決定，其緩沖區(qū)需要的空間遠遠大于子流模型。

3 實驗結(jié)果

根據(jù)靜態(tài)匯聚節(jié)點、移動匯聚節(jié)點和延遲移動匯聚節(jié)點的策略在網(wǎng)絡環(huán)境的Matlab下進行了實驗。本文嘗試了不同的參數(shù)，例如節(jié)點的數(shù)量，可能的接收器的位置和參數(shù)的能耗模型的數(shù)目。在所有的實驗中，本文使用GLPK 求解線性規(guī)劃問題。實驗參數(shù)如下：傳感器節(jié)點數(shù)為｛100，200｝，匯聚節(jié)點站點數(shù)為｛5，6，7，8，9，10，15，20，30｝，路徑能源消耗比為｛2，3｝，初始能量為500J，數(shù)據(jù)收集速率為500bit／s。

根據(jù)移動匯聚節(jié)點的位置來比較各種模型的網(wǎng)絡生命周期。節(jié)點的數(shù)量設置為100或200，路徑損耗指數(shù)e為2或3。覆蓋區(qū)域半徑設置得足夠大，且總是覆蓋整個傳感器領域。通過多次循環(huán)實驗，移動匯聚節(jié)點模型和移動延遲容忍模型的生命周期明顯比靜態(tài)匯聚點模型的生命周期長。如圖2所示，移動匯聚節(jié)點模型的生命周期為靜態(tài)匯聚節(jié)點模型的100%～200%。而移動延遲容忍模型的網(wǎng)絡生命周期與靜態(tài)匯聚模型相比，提高了200%～1000%。此外，可以看出網(wǎng)絡生命周期的延長曲線為線性增長，隨著節(jié)點數(shù)量的增加，移動匯聚節(jié)點的停留位置增多，算法性能差距可能更大。

圖2 相對生命周期對比Fig.2 Comparison of relative lifetime

4 結(jié)束語

提出了一種基于移動匯聚節(jié)點的方式來延長傳感器網(wǎng)絡生命周期的策略。實驗結(jié)果證明，移動匯聚節(jié)點模型的生命周期為靜態(tài)匯聚節(jié)點模型的100%～200%。而移動延遲容忍模型的網(wǎng)絡生命周期與靜態(tài)匯聚節(jié)點模型相比，提高了200%～1000%。延遲容忍模型相比傳統(tǒng)的靜態(tài)匯聚節(jié)點模型，在延長網(wǎng)絡生命周期的效果上有顯著的提升。然而，隨著節(jié)點數(shù)的增加，匯聚節(jié)點的通信半徑的增大，延遲容忍模型也存在相應的問題。延遲容忍模型需要大量的緩沖空間對數(shù)據(jù)進行儲存，提高了對節(jié)點緩沖空間的要求。因此，如何有效地利用節(jié)點緩存空間，以及移動匯聚節(jié)點的合理路徑規(guī)劃問題也是今后需要研究的一個重要方向。

［1］Popa L，Rostamizadeh A，Karp R，et al.Balancing traffic load in wireless networks with curveball routing［C］∥Proceedings of the Proceedings of the 8th ACM International Symposium on Mobile ad Hoc Networking and Computing，ACM，2007：170－179.

［2］Li J，Mohapatra P.An analytical model for the energy hole problem in many－to－one sensor networks［C］∥Proceedings of the IEEE Vehicular Technology Conference，IEEE，2005：2721－2725.

［3］Wang Z M，Basagni S，Melachrinoudis E，et al.Exploiting sink mobility for maximizing sensor networks lifetime［C］∥Proceedings of the System Sciences，2005HICSS＇05Proceedings of the 38th Annual Hawaii International Conference on，IEEE，2005：287a.

［4］Luo J，Hubaux J－P.Joint mobility and routing for lifetime elongation in wireless sensor networks［C］∥Proceedings of the INFOCOM 2005 24th Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings IEEE，IEEE，2005：1735－1746.

［5］Shi Y，Hou Y T.Theoretical results on base station movement problem for sensor network［C］∥Proceedings of the INFOCOM 2008 The 27th Conference on Computer Communications IEEE，IEEE，2008：1－5.

［6］Chang J H，Tassiulas L.Maximum lifetime routing to mobile sink in wireless sensor networks［J］.IEEE／ACM Transactions on Networking，2004，12（4）：609－619.

［7］Shah R C，Roy S，Jain S，et al.Data mules：Modeling and analysis of a three－tier architecture for sparse sensor networks［J］.Ad Hoc Networks，2003，1（2）：215－233.

［8］莊偉，宋光明，魏志剛，等.具有機動能力的無線傳感器網(wǎng)絡節(jié)點的設計與實現(xiàn)［J］.吉林大學學報：工學版，2007，37（4）：939－943.Zhuang Wei，Song Guang－ming，Wei Zhi－gang，et al.Design and implementation of a mobile node for wireless sensor networks［J］.Journal of Jilin University（Engineering and Technology Edition），2007，37（4）：939－943.

［9］王毅，張德運，馬新新，等.無線傳感器網(wǎng)絡傳感器節(jié)點動態(tài)功耗管理方法［J］.吉林大學學報：工學版，2008，38（4）：880－885.Wang Yi，Zhang De－yun，Ma Xin－xin，et al.Novel dynamic power management of sensor node in wireless sensor networks［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（4）：880－885.

［10］孫強，徐晨，黃勛.無線傳感器網(wǎng)絡移動匯聚節(jié)點的研究［J］.通信技術(shù)，2008，40（11）：173－175.Sun Qiang，Xu Chen，Huan Xun.Research on mobile sink of wireless sensor network［J］.Communications Technology，2008，40（11）：173－175.

［11］孟中樓，王殊，王騏.分簇式無線傳感器網(wǎng)絡匯聚節(jié)點移動策略研究［J］.華中科技大學學報：自然科學版，2009（6）：67－70.Meng Zhong－lou，Wang Shu，Wang Qi.Research on the moving strategy for mobile sink in cluster wireless sensor networks［J］.Journal of Huazhong University of Science and Technology（Nature Science Edition），2009（6）：67－70.

［12］Basagni S，Carosi A，Melachrinoudis E，et al.A new MILP formulation and distributed protocols for wireless sensor networks lifetime maximization［C］∥Proceedings of the Communications，2006ICC＇06 IEEE International Conference on，IEEE，2006：3517－3524.