基于地理路由和參與者協作模型的WSAN的通信機制

趙海軍，賀春林，蒲斌，崔夢天

（1. 西華師范大學計算機學院，四川 南充 637009；2. 西南民族大學計算機科學與技術學院，四川 成都 610041）

1 引言

無線傳感器和參與者網絡（WSAN, wireless sensor and actor network）[1]是一種分布式異構設備無線通信系統，異構設備主要是傳感器和參與者，其網絡物理結構如圖1所示。這里的參與者不同于傳統的執行器的概念，它除了能夠通過幾個執行器在環境中工作外，還是一個執行與網絡相關功能的單一網絡實體，即接收、發送和轉發數據。在大多數應用中，參與者是資源豐富的超大處理能力和高傳輸功率設備及長壽命的電池。

圖1 無線傳感器和參與者網絡的網絡物理結構

WSAN中的不少應用與加強和補充現有的傳感器網絡應用有關。在這些應用中，執行活動主要是通過啟用或擴展其監控能力來增強傳感器網絡的操作。例如，移動參與者可以準確地部署傳感器，實現對環境的自適應采樣，從近距離的傳感器拾取數據、緩沖數據，并將數據發送到有線接入點，或者執行能量收集[2-4]。

關于WSAN的研究，文獻[5]針對靜態WSAN的通信和協作問題提出了一種框架，并提出了傳感器-參與者協作和參與者-參與者協作的概念，以及集中式最佳解決方案和分布啟發式解決方案。文獻[6]提出了一種適用于無線傳感器網絡的單純事務管理模型，主要包括事務并發控制策略和事務原子提交協議。在事務并發控制方面，結合無線傳感器網絡的特點使用了輕量級的向前驗證的樂觀并發控制；在事務原子提交協議方面，提出了基于緩存和定時器的二階段提交協議，為參與者提供了緩存機制，有效利用協調者的廣播信息，降低能量消耗。在協調者和參與者中加入了定時器，定時器觸發后會提供事務處理統一的結果（提交或撤銷）；此外，還為協調者加入了心跳算法來提高協議的可靠性；但該模型最大的不足是未考慮協調者和參與者之間的通信機制問題。文獻[7-8]研究了傳感器網絡中的實時通信問題，但并未就傳感器和參與者之間的數據交換和協作進行研究。文獻[9]針對傳感器網絡中數據發送的能量消耗和時延之間的權衡進行了研究。文獻[10-11]采用地理位置信息對傳感器網絡的可擴展路由進行了研究，以減少傳感器之間協作所需要的信號強度和能耗。

本文針對有移動參與者的 WSAN中的協作和通信問題進行研究，提出的主動位置管理方案以最小能量消耗來管理參與者的移動性。參與者廣播其位置的更新，基于Voronoi圖限制其范圍，而傳感器基于先前接收到的更新卡爾曼濾波來預測參與者的移動；然后得到一種基于地理路由的最佳能量感知轉發規則作為傳感器-參與者之間的通信，并采用功率控制來控制數據傳輸過程的時延，通過迫使多個參與者成為在事件區域中生成流量的接收者來解決網絡擁塞；最后基于事件特征提出了參與者-參與者之間的協作模型來對參與者之間的移動進行協調，以最佳地完成任務。仿真結果表明，本文提出的關于WSAN的通信機制是有效的。

2 傳感器和參與者的位置管理

假設網絡由NS個傳感器和NA個參與者構成，且NS＞＞NA。每個傳感器配備一個低數據速率的無線接口，每個參與者配備2個無線發射器，一個低數據速率發射器用于與傳感器進行通信，一個高速率無線接口用于參與者-參與者之間的通信。

根據傳感器網絡路由算法[5,12-13]，本文基于地理路由范式來實現傳感器-參與者之間的協作管理，因為這樣可以在不增加信令開銷的情況下對網絡規模進行擴展，且路由判決本質上是局部化的。但在具有移動節點和多個接收者的網絡中，還依賴于有效的位置管理策略，才能夠提供任何時刻與移動節點位置相關的節點。為此，本文提出了一種主動位置管理方法，該方法基于移動參與者發送給傳感器的更新消息。在 WSAN中，每個參與者是一個等效的信息接收者，因而傳感器-參與者之間的通信是局部的，即每個傳感器發送信息給它的最近參與者。因此，在空域中，廣播可以基于 Voronoi圖[14]進行限制；同時，參與者的移動在某種程度上是可預測的，因為它是由參與者-參與者之間的協作過程驅動的。因而在時域中，位置更新可以被限制到參與者的位置，這個位置不能在傳感器一側被預測。當參與者的實際位置“遠”于根據過去測量值在傳感器上可預測的位置時，位置更新將在參與者上被觸發。

2.1 限制廣播空間

本文采用Voronoi圖來限制由參與者發起的位置更新范圍。一組離散站點的Voronoi圖將平面分割成一組凸多邊形，使多邊形內的全部點都僅離一個站點最近。如果一個傳感器s的位置位于一個參與者a的Voronoi圖單元中，就說傳感器s由參與者a控制。每個參與者負責其Voronoi圖單元中傳感器的位置更新，并調節其功率，以限制超出其Voronoi圖單元的最遠點的干擾，因此每個傳感器希望從控制它的參與者處接收位置更新。如果參與者能夠在一跳中到達其Voronoi圖單元中的全部傳感器（這在許多實際情況下是可能的），則大部分的能量消耗在參與者上。

2.2 限制廣播時間

在二維坐標系中，第i個參與者的動態運動模型可以采用狀態空間法[15]得到其等價的離散時間動態方程，即

式(1)表示系統的狀態轉移方程，描述了第i個參與者在時間步k-1和k之間的運動，其中，有

時間步k與第i個參與者觀察到的位置和狀態有關，可用測量方程表示為

卡爾曼濾波[16]提供了一組高效計算的遞歸方程來估計參與者的動態運動過程的狀態，本文利用它來估計參與者的位置，并在傳感器上預測參與者的位置，從而減少信息交換。參與者的位置可以基于在參與者上得到的測量值zik并在參與者的Voronoi圖單元中的傳感器上進行估計和預測，通過參與者廣播。在時間步k，第i個參與者的Voronoi圖單元中的每個傳感器s根據式(4)更新狀態（參與者的位置和速度）。

式(4)描述了在接收測量值之前（先驗估計值）傳感器s如何預測參與者的狀態。注意，控制輸入在傳感器上是未知的，同時被用于參與者更新狀態；然后，傳感器s預先預測協方差矩陣，在接收到來自參與者的測量值后，更新卡爾曼增益（如式(5)所示），并根據測量值校正狀態估計值（如式(6)所示）和協方差矩陣（如式(7)所示），即

在每個時間步k，每個參與者都試圖在它的Voronoi圖單元中的傳感器上執行預測過程，通過對新的測量值濾波，計算其實際新的位置，并廣播新的測量值如果傳感器s在時間步k沒接收到位置更新，則假設即預測的位置與參與者實際的新的位置一致，在此基礎上，按式(5)～式(7)更新參與者的狀態估計值。

3 傳感器-參與者之間的通信

本文提出了一種可靠性概念，即由一個參與者感知到的事件可靠性r是在一個判決間隔中的可靠數據分組與接收到的全部數據分組的比值，如果在給定的時延范圍內數據分組被接收，則認為這個數據分組是可靠的；事件可靠性閾值rth是所要求的最小的事件可靠性。本文的目標是當數據必須在一個給定的時間限制內以一個給定的可靠性閾值rth交付時，換取的能量消耗時延。

3.1 基于功率控制的能量時延調節

大多關于地理路由的研究主要考慮貪婪轉發，即將數據分組轉發給最接近目的端的節點，然而，這通常需要選擇將轉發節點連接到位于傳輸范圍邊界附近的鄰居。當考慮一個實際的物理層時，這種連接很可能是不穩定的，容易產生高分組差錯率，故本文提出在節能鏈路上轉發數據分組，使在每個單跳上的能量消耗達到最小化。本文不考慮大多數路由研究所采用的單位圓盤圖假設，而是考慮一個更精確的連通模型，即首先得到在快速衰落信道下的節能轉發距離，然后提出一種通過增加發射功率來減少端到端時延的機制。

考慮轉發器vi和vj之間的通信，用dij表示2個轉發器之間的距離，則vj接收由vi發送的數據分組的概率可以表示為

其中，Eamp是一個常數，單位為J/(bit?m)，Emarg是包含允許期望分組差錯率項的調整項，單位為J/(bit?m)，表示在有α損耗下每米每比特所需要的能量。較高的Emarg值會導致較高的能量消耗，同時增加接收器成功接收的概率，減少預期的重發次數。

考慮節點vi向其距離為D的目標參與者ak轉發一個數據分組，且鏈路指標E=2Eelec+Eampdα，其中Eelec是收發器電路發送或接收1 bit所需的能量，單位為J/bit，則端到端能量消耗可以表示為

其中，P(vi,ak)表示vi和ak之間的路徑。理想情況下，當數據在一組位于連接源和目的線路節點上（節點間距離等距dopt）轉發時，端到端能量消耗就達到最小化。通過將式(10)代入式(12)，并考慮重發可得到

一個穩定點的充分條件是一個極小值，該極小值通過Hessian ?2Ee-e在穩定點計算得到。最佳轉發距離dopt與D無關，D為轉發節點和目的端之間的距離。式(13)可以解釋為距離無關和距離有關的能量消耗之間的最佳折中，并且適合于局部轉發規則。在理想信道情形且Emarg=0時，當時，式(13)就達到最小化。

當Eelec=50 nJ/bit，Eamp=100 pJ/(bit.m)，α=2.5時，對于理想信道來說，最佳轉發距離dopt=13.47 m。求解式(13)得到一個瑞利衰落信道上的dopt=8.00 m且Eoptmarg=86 pJ/(bit.m)，即Eoptmarg≈Eamp。因此，當在一個瑞利衰落信道上的期望最佳轉發距離比理想信道情況低時，所需的發射功率就更高。

于是得到結論：能量最優路徑是通過將數據分組轉發給位于dopt（單位為 m）之外連接轉發節點和目的節點的線路上來得到的，稱這個二維平面上的點為最佳轉發點。一個實用的轉發規則應該選擇與這一點有最小距離的下一跳。當下一跳比最佳轉發點更接近目的節點時，期望的能量消耗會明顯增加。因此，在這種情況下，把下一跳選擇為離最佳轉發點最近的節點，即那些不比最佳轉發點更靠近目的節點的節點。

可靠性可通過參與者反饋信息來控制。當事件發生時，全部傳感器都以最大轉發范圍開始傳輸。然后，根據觀察到的參與者反饋的可靠性，傳感器可以減小它們的轉發范圍，直至可靠性接近所要求的事件可靠性閾值rth，或達到最佳轉發范圍。當在最大轉發范圍內觀察到的可靠性較低時，參與者就啟動網絡層擁塞控制程序。

3.2 基于參與者驅動的擁塞控制

每當參與者ai檢測到由過度時延和數據分組丟失造成非常低的可靠性時，則選擇另一個參與者重新發送來自其Voronoi圖單元中的一半傳感器的流量給這個參與者。每個參與者ak被ai分配一個權值wk，這個權值用于度量它成為一個在部分事件區域得到的流量接收者的合理性。權值

1) 擁塞因子ηk(0≤ηk≤1)。這個值反映了在參與者ak上觀察到的可靠性，即如果r＜rth-ε，則ηk=1，當r-rth增大時，ηk單調減小；對于那些沒接收流量的參與者來說，ηk=0。其中ε表示可靠性的適當裕量，以避免不穩定。

2) 指向性因子δk。這個值反映了參與者ak相對于參與者ai和事件區域中心的相對角位置。

圖2說明了參與者ai正從事件區域的一部分接收數據的情況。圖2中，Cev為事件區域的中心，表示傳感器位置的加權和，位于ai的Voronoi圖單元中的事件區域的部分中心為Cev,i。在圖 2給出的事例中，事件區域被分成兩部分，且另一個參與者從事件區域的第二部分接收數據。在一般情況下，事件區域在多個參與者間被劃分，假設全局事件的中心Cev已由參與的參與者合作重建，這樣，將給予位于關于Cev,i的ai的同方向的參與者更高的權值，因為這將導致在ai方向的流量增加，或在關于Cev,i的Cev方向的流量增加，從而增加事件區域的流量；相反，對于遠離這2個方向（圖2中的最佳方向）的那些參與者的指向性因子應該是最大的。角度α、β和θk分別描述了Cev,i與ai、Cev和ak的相對角位置。

圖2 指向性因子δi的計算

參與者ak的指向性因子的計算式為

一個擁塞的參與者ai選擇具有最小權值wk?的最佳參與者ak?。然后，參與者ai計算并告知ak?的一個新的虛擬位置給其 Voronoi圖單元中的傳感器。虛擬位置必須位于連接參與者的實際位置xk?和事件區域Cev,i的線路上，而且對應于Cev,i中的一半傳感器更接近于ai的點，而另一半傳感器更接近于ak?。每個傳感器將選擇其接收參與者，對于參與者ak?，采用虛擬位置而實際位置xk?仍用于執

3) 距離因子Δk。它是參與者距離事件中心Cev,i的距離，歸一化為監控區域的直徑，即當距離最大時，Δk=1。行實際的轉發功能。虛擬位置允許以這種方式最佳地劃分傳感器，只有那些更接近ak?的傳感器重新發送它們的流量給ak?，并通知傳感器。這個過程由在流量分割后仍然擁擠的參與者遞歸運用。

4 參與者-參與者之間的協作通信

本節構建多個參與者任務分配問題，其目標是協調它們的移動性。一般而言，選擇最好的參與者構成參與者團隊，并控制它們向作用區域移動。

通過上述分析可知，生成讀數的傳感器的位置定義了事件區域。作用區域表示參與者應當起作用的區域，并通過處理事件數據來識別。通常情況下，事件區域和作用區域可能是不同的。

根據從作用區域收集到的事件的特征，在事件空間Ω中發生的每個事件ω可以用數組Ψ(ω)={F(ω),Pr(ω),A(ω),S(ω),I(ω),D(ω)}來描述，其中，F(ω)描述事件的類型，即事件所屬的類別；Pr(ω)描述的是優先級；A(ω)描述的是事件區域，單位為 m2；S(ω)描述的是作用區域，單位為m2；I(ω)描述的是強度，單位為 J/m2；D(ω)描述的是作用完成的時間限制，即從事件被感知到完成相關作用的最大允許時間，單位為 s。這些確定每個發生事件的特征參數由接收傳感器信息的參與者分布式重構，并構成多個參與者任務分配問題的輸入；多個參與者分配問題包括選擇一個參與者團隊和它們的速度，以最佳地劃分作用工作量，使完成作用所需的能量最小化，同時滿足作用完成的約束時間。盡管參與者是資源豐富的節點，但作用和移動所需能量的數量級要高于通信所需的數量級，因此，重要的是要節省作用和移動的能量，以延長參與者的壽命周期。本文把多個參與者的分配問題構建為一個混合整數非線性規劃（MINLP, mixed integer non-linear program）。

首先假設：1)執行作用的能量（作用和移動能量）比通信所需要的能量要高；2)由于缺乏資源，只有當與更高優先級的事件相關的作用無法完成時，才執行任務再分配。

ηfa：參與者a在一個事件類型f∈F(ω)上執行的效率，即用于作用區域的作用能量所產生的效應與作用能量本身之比。參與者a在事件ω發生時得到的可用能量，單位為J。

TC：協作時延，即處理事件數據、重建事件本身，并通過求解問題來選擇參與者團隊所需要的時間，不依賴于事件，單位為s。當事件ω發生時參與者的子集，即沒有分配給在與先前發生事件相關聯的作用區域執行的參與者。發送數據分組給參與者a的資源總數，而是一個懲罰函數，單位為J，它對參與者a的選擇進行加權，參與者a接收來自源的數據，是一個執行團隊的一部分。懲罰函數隨的增加而單調增加。

尋找

最小化

滿足條件

約束式(17)確定了參與者a移動到由發生事件確定的作用區域所需要的能量，是移動所需的功率和以給定速度到達作用區域所需的時間的乘積；時間為參與者離作用區域的距離與所選擇的速度的比值，即式(18)；約束式(19)限制了每個參與者的速度范圍；當參與者a是一個參與者團隊的一部分時，約束式(20)確定了a完成作用所需要的能量；約束式(21)確保所選擇的團隊能夠完成分配的任務，給定組成團隊的參與者的特點和事件的范圍及強度；約束式(22)限制執行完成時間和需要移動參與者團隊所需要的時間總和要小于作用完成時間與協作時延之差；約束式(23)確保每個參與者有非負的剩余能量；約束式(24)保證至少有一個參與者作用于告知的作用區域。

5 方案性能評價及分析

5.1 傳感器-參與者之間的通信

仿真平臺采用J-Sim[17]，J-Sim采用新的進程驅動機制，且兼容離散事件的驅動。J-Sim采用分裂對象模型：可用Java語言編寫網絡組件，采用TCL腳本來描述仿真場景、拓撲結構及鏈路中使用的算法和協議，并對這些對象進行配置和組合；通過 J-Sim可以很容易建立網絡拓撲、節點結構和通信行為，從而實現網絡仿真，達到評價網絡算法和協議的目的。

對于傳感器-參與者之間的通信，傳感器執行3.1節中所描述的地理轉發算法，MAC層基于CSMA/CA，物理層執行本文提出的功率控制過程并設定帶寬和功耗參數，類似于IEEE 802.15.4兼容無線電。監控區域是一個200 m×200 m的正方形區域，隨機部署200個傳感器。傳感器的最大傳輸范圍設置為40 m，帶寬設置為250 kbit/s。傳感器發送56 B的數據分組，采用每秒一個數據分組的報告率，隊列大小設置為20個數據分組，仿真執行持續400 s。

圖3和圖4分別為中、低流量情形下（即事件分別圍繞中心40 m和20 m的范圍）仿真運行得到的平均功率消耗和端到端時延與轉發范圍的關系。事件區域為圓形，且中心在（100 m, 100 m），在事件區域內的傳感器報告測量值給參與者。在中流量情形下，需要對位于事件區域內的7個傳感器求平均；在低流量情形下，大約有25個傳感器。由圖3和圖4可知，低流量情形下的平均功率消耗和端到端時延都低于中流量情形，而且在中、低流量情形下，端到端時延一開始隨著轉發范圍的增大而持續降低，這是以增加功率消耗來換取的，而后趨于穩定。

圖3 中、低流量情形下平均功率消耗與轉發范圍的關系

圖4 中、低流量情形下端到端時延與轉發范圍的關系

圖5～圖7為高流量情形即事件范圍設置為60 m（相當于平均57個傳感器）且事件區域完全位于一個單一的參與者 Voronoi圖單元里得到的仿真結果。仿真結果比較了一個參與者（對應于不采用3.2節所設計的擁塞控制程序）和2個參與者（對應于采用 3.2節所設計的擁塞控制程序）接收事件區域生成流量時的平均功率消耗、端到端時延和分組丟失率。

圖5 高流量情形下平均功耗與轉發范圍的關系

圖6 高流量情形下端到端時延與轉發范圍的關系

圖7 高流量情形下分組丟失率與轉發范圍的關系

從圖5～圖7可以看到，在不采用本文提出的擁塞控制程序時，由于事件區域本身是擁擠的，因此數據分組被丟棄的比例較高，如圖7所示，大約為14%～43%。同時端到端時延平均增加了約1 s，且不易通過改變轉發范圍來控制，如圖6所示。相反，當采用本文提出的擁塞控制程序時，將事件數據在2個參與者之間進行劃分，擁塞可以大大降低，這是由于大多數擁塞和分組丟失發生事件區域的多個節點嘗試同時發送，當在事件區域的另一側的第二個參與者接收數據時，擁塞就得到了顯著的改善，因為流量從事件區域被轉移了，所以分組丟失率接近于0，如圖7所示，平均時延也降低了近2個數量級，且可以采用功率控制來調節，如圖 6所示。重要的是，即使第二個參與者遠離事件區域，數據分組過早地在它們的源參與者路徑上被丟棄，功耗也會通過擁塞控制程序被降低，主要是由于在MAC層上減少了數據分組的重傳，如圖5所示。

5.2 參與者-參與者之間的協作通信

假設參與者隨機部署在200 m×200 m的區域，事件強度I=0.5 J/m2，作用范圍S=42π m2隨機出現在整個區域，設置作用完成時間限制D(ω)和協作時延TC分別為14 s和1 s。考慮同類參與者的情形，其β=0.05 W/(m.s-1)，γ=1.5，效率η=1，作用功率l=1 W/m2，初始能量E0=1 000 J，速度為3～12 m/s。

圖8和圖9分別為能量消耗和時延與最大團隊規模之間的關系，圖10為能量消耗與構成一個團隊的參與者的數目固定且等于團隊大小的關系。可以看出，當參與一個執行團隊的參與者數目最優以使總的能量消耗（即移動能量EM和執行能量EΩ的總和）最小時，則至少需要3個參與者來完成執行，如圖8所示。且總的執行時間正好是作用完成時間限制D(ω)減去協作時延TC，即13 s，如圖9所示。問題趨于使參與的參與者數目最小化，并將更高的速度分配給那些更接近作用鄰區域的參與者。這可以通過考慮每次一個參與者需要移動所消耗的一個固定大小的功率來解釋，無論其速度如何。相反，當全部參與者必須成為團隊的一部分時，執行時間是以犧牲能量消耗為代價來減少的，如圖10所示。

圖8 能量消耗與最大團隊規模的關系

圖9 時延與最大團隊規模的關系

圖10 能量消耗與團隊規模的關系

5.3 與文獻[6]提出的單純事務管理模型的比較

本節給出采用本文提出的通信模型與文獻[6]提出的單純事務管理模型在中等流量情形下（大約25個傳感器）的比較結果。圖11為2種模型在平均時延、節點能量消耗和分組丟失率方面的仿真結果。

圖11 本文提出的通信模型和文獻[6]提出的單純事務管理模型的比較

從圖 11(a)和圖 11(b)可以看出，由于本文提出的通信模型既考慮了節點間的數據路由和交換問題，同時也考慮了節點和參與者之間及參與者和參與者之間的通信機制，因此在平均時延和節點能量消耗方面均優于文獻[6]的單純事務管理模型，而且當達到一定節點數時，隨著節點數的增加（對應流量增加），本文提出的通信模型在平均時延和節點能量消耗方面增加并不明顯，說明本文提出的通信模型是頑健的和可擴展的。

圖11(c)為2種模型在高流量和事件范圍20 m及一個參與者和2個參與者情形下得到的分組丟失率仿真結果。由圖11可知，盡管2種模型的分組丟失率隨著傳感器節點數的增多而增大，但本文提出的通信模型無論在一個參與者還是2個參與者時都要低于文獻[6]提出的單純事務管理模型。特別是在一個參與者時，由于文獻[6]提出的單純事務管理模型使用了節點緩存機制，隨著傳感器節點數的增加，需要維持各個節點的提交矩陣，導致動態內存消耗增加而出現緩沖溢出，從而增大分組丟失率；而在2個參與者時，當傳感器節點數較少時，文獻[6]提出的單純事務管理模型盡管使用了節點緩存機制，但2個參與者有足夠的緩存接納各個節點的提交矩陣，所以其分組丟失率非常接近本文提出的通信模型的分組丟失率，但仍高于本文提出的通信模型的分組丟失率。

6 結束語

本文研究了具有移動參與者的無線傳感器和參與者網絡中的通信問題，并針對傳感器-參與者之間和參與者-參與者之間的協作通信問題提出了有效的解決方案。首先，采用傳感器最小能量消耗，提出了一個主動位置管理方案來處理參與者的移動性；然后，基于地理路由，提出了一種傳感器-參與者之間通信的有效節能解決方案，并給出了如何基于功率控制來控制數據傳輸過程的時延，以及如何通過迫使多個參與者共享事件區域產生的流量來處理網絡擁塞；最后，基于事件的特征，提出了一種參與者-參與者之間的協作通信模型來協調它們之間的運動。結果表明，本文提出的關于 WSAN的通信機制在減少端到端時延、能量消耗和分組丟失率方面是有效的。未來將針對選擇最佳參與者來形成參與者團隊，以執行特定要求的作用，并驅動參與者向相關的區域移動進行深入研究。