交替活躍的部分連接網絡休眠調度策略研究

摘要：提出基于交替活躍的部分連接網絡的休眠調度策略，無須進行拓撲控制，支持較高的休眠/活躍比率，顯著提高了網絡平均壽命。給出了滿足延遲要求的休眠時間表的確定方法。提出簇內休眠相位同步和簇間相位次序調整的主動調節方法。仿真表明，該方法顯著降低了端到端的延遲。

關鍵詞：部分連接網絡；休眠調度；延遲；仿真

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)07－0270－03

無線Ad hoc網絡具有靈活部署的優勢，擁有巨大的應用潛力。組成網絡的節點通常受到電源供給和硬件資源的限制，但大量的節點協同工作，卻可以提供豐富的功能。因此在實際的Ad hoc網絡應用中，需要在節點（個體）的資源限制和網絡（群體）的性能之間作出折中。盡管無線接口的硬件低功耗設計有了長足發展，通信功耗仍然占功耗中的最大比例[1]。在滿足性能要求的前提下，降低無線通信功耗是無線Ad hoc網絡面臨的最大挑戰。

最直接的節省通信功耗的方法就是對節點的通信狀態進行調度。由于無線Ad hoc網絡中，發送、接收和偵聽消耗的功耗相差不大，只有徹底關閉無線收發電路，才具有較好的節能效果。通過節點調度，讓節點交替地處于活躍和休眠狀態的交替活躍模式是節能的有效方法。但是較低的活躍程度會造成丟包和響應速度降低，甚至成為非連通的網絡。

由于目前大多數的Ad hoc路由基于完全連接的拓撲假設，當網絡是非連通時無法工作。為避免節點交替活躍造成的連通性破壞，同時避免部分節點能量過度支出，休眠調度時，需要進行拓撲控制。節能協同技術是一種有效的節點調度方法，堅持完全連接的假設，構造連通支配集。其中的節點保持活躍，形成完全連接的骨干網。但是，為了保證網絡的完全連接，休眠節點的數量和休眠時間均受到限制，影響了節能效果，而且拓撲控制的算法也會造成額外開銷。

另外一種可行的方法就是拋棄完全連接的假設，節點按照獨立的休眠—活躍時間表進行交替切換，所有節點可以得到公平的休眠機會。其控制簡單，節省了調度的能量消耗。同時，由于不需要保證網絡的完全連接，允許更多的休眠節點數量和更長的休眠時間，網絡整體的壽命得到延長。但是大量的節點隨機地處于交替活躍模式，會使網絡的連通性無法保證，成為部分連接的網絡。為此，本文提出能夠適應部分連接的網絡異步路由轉發方式。當下一跳休眠時，包會在本節點延遲等待；當下一跳恢復活躍時，繼續轉發。在連通性無法保證的部分連接網絡中，也能維持系統的性能。該方法雖然引入了一定的延遲，但是由于無須拓撲控制，允許更高程度節點休眠，適用于強調節能而對實時性要求不高的領域，如土壤監測、生態監測、氣象監測等非實時的應用。

1相關研究

能量問題是無線Ad hoc關心的重要問題。降低通信功耗是主要途徑。目前對于通信產生的功耗分析的研究中，建立了很多無線通信的能量模型。節點在不同狀態下的能量消耗具有差異。文獻[2]給出了傳感器網絡射頻電路RFM的功耗模型，接收、發送和空閑的功率在9~12 mW，休眠消耗功率僅為0.016 mW。文獻[3]給出了802.11無線網卡的功耗模型，接收、發送和空閑的消耗功率分別為1 000 mW、1 400 mW、830 mW，休眠狀態的功率為130 mW?？梢?，即使在空閑狀態，能量的消耗也相當大。有效控制通信能量開銷就是要讓盡量多的節點在盡可能多的時間內處于休眠狀態。

通過精心設計的算法自動選擇一部分節點保持活躍，而讓另一部分節點休眠是有效的途徑。文獻[4]給出了節點協同算法，構造最小連通支配集；這一部分關鍵節點組成連通骨干，完成路由轉發，而讓其他節點休眠，既縮小了路由查找范圍，又能夠顯著降低能量消耗。但是過少的關鍵節點會降低網絡的響應速度和性能。文獻[5]給出了擴大的連通支配集生成算法，可以在不降低性能的情況下讓網絡節點交替休眠，比較適合節點密度較大的網絡。為了避免選擇的活躍節點一直工作，節點需要交替休眠，每次交替均需要重新生成支配集，造成較大開銷。

另外一種休眠方式就是每個節點維護一個活躍—休眠時間表，所有節點都均等地進行自主休眠。AFECA方法[6]采用節點隨機休眠的策略，休眠時間與鄰居節點的數量呈正相關。Stemm和Katz提出了利用應用層的指示信息確定節點的時間表[7]。但是自主的分布式休眠調度會使網絡的連通性被破壞，對于需要完全連接拓撲的同步方式路由是十分不利的。Ramanathan和Rosales－Hain等人提出調節發送功率的方法維持連通性[7]，拓撲控制算法會受到網絡的支持限制。而文獻[8]則放棄了完全連接的假設，讓更多的節點休眠，不需要維持網絡的連通性；雖然能夠顯著降低能量開銷，但是會造成延遲的增加。

采用延遲轉發的異步方式進行通信，不對網絡的連通性有要求，無須拓撲控制，允許更多節點休眠，延長了網絡壽命。對異步通信方式的延遲進行估計，依據計算結果，設計了主動和被動方式的休眠調度算法，顯著降低了延遲。

2交替活躍網絡延遲估計

根據端到端的延遲分布函數，可以估計在容忍的延遲時間內獲得的包遞交率，也可以按照應用的遞交率的性能需求，推算延遲等待的時間；根據端到端的平均延遲的計算可以得到節點按照當前休眠時間表進行調度，也可以獲得系統的響應時間。這兩個計算結果對強調節能休眠的Ad hoc網絡的節點調度具有參考意義和指導作用，也是本文休眠調度方法的理論依據。

3休眠—活躍調度的方法

與協同調度方法不同的是，在交替活躍網絡中不需要拓撲控制讓活躍節點構成路由骨干網，而是讓節點平等地按照各自的時間表進行休眠—活躍的交替。休眠活躍調度的主要問題就是確定和調整節點的時間表。

時間表的調整有兩種方式，即主動和被動。在主動方式中，節點通過局部信息自適應地調整時間表，使得鄰近節點的時間表盡量重合，即同時活躍或同時休眠；而距離較遠的節點休眠的交替相位按照一定的順序，如包轉發方向依次滯后。這種局部同步、全局排序的方法，能夠有效地適應異步延遲轉發方式。

通過分簇算法將網絡分為若干鄰接區域；簇首領周期性地廣播時間表以同步區域內部節點的時間表。其中包含一個簇首領時間戳，表示其已經保持活躍的時間。簇內節點收到后，會根據自己已經活躍的時間與該時間戳進行比較，并使具有相同的活躍交替相位。簇內時間表同步可以使節點同時活躍的概率增加。

對于簇間調整過程如下：簇A首領周期性地廣播時間表，當簇B的節點收到時，查找路由表。如果A包含在B的路由中，且處于上游鏈路，則使自己的相位滯后于簇A的相位，否則相位超前于簇A的相位，滯后的幅度為簇A和簇B平均休眠時間（1/μ）的1/k；如果不在路由表中，或者存在兩條路由條目且A、B互為上游鏈路，則不調整。經過調整后，在包的轉發方向上，每跳的平均等待延遲從1/μ降低為1/（k×μ），端到端延遲顯著降低。

被動調度方式的調節方法目的是使網絡在不同情況下呈現不同的活躍特性。網絡的應用層對響應的需求會隨時變化（如平時和戰時區別、通常時期和應急時期的區別），節點的休眠表需要進行相應的調整。例如在應急情況時，網絡需要具有較好的響應速度，網絡節點的活躍程度應當提高；而對于平時情況，網絡可以延長休眠。當應用層對于性能和響應時間的需求發生變化，被動調節方法可以動態修改節點休眠—活躍時間表，以調節網絡性能和時間特性。根據第2章的計算結果，可以通過調節μ和λ達到調節延遲時間和遞交率的目的。另外，被動調度還包括依據應用對網絡的延遲時間要求，在同步轉發方式和異步轉發方式之間動態選擇。當應用需要較高實時性時，節點根據延遲計算得到較高的μ。這時，會觸發被動調度過程，選擇同步轉發方式；反之，采用異步轉發方式。

4仿真和結果分析

在仿真中，考察場景：100個節點隨機拋撒均勻分布于10 km×10 km的平面區域，所有節點均按照交替活躍模型以間歇性方式工作。ON和OFF狀態到達時間間隔服從負指數分布，參數分別為μ=1/10和λ=1/100。位于區域上方的源節點node_0~node_5的應用層的CBR業務源，分別向位于區域下方的node_94~node_99發送數據包，發送速率為2 packet/s，包到達容忍延遲時間為T，發包持續時間為2 h，平均包長度500 Bytes，平均路徑長度為13跳。

當所有節點按初始化的時間表進行交替活躍的工作，平均延遲為12.11 s（計算估計值為11.82 s）。當進行簇劃分（簇直徑為2跳），平均每條路徑經過5.5個簇，經過簇內調節后，平均路徑長度降低為5.5跳。根據計算模型得知，平均延遲計算估計值為5 s，仿真結果如圖3所示。穩態后平均為5.2 s。當啟動簇間調節過程后，理論延遲k降低5.5倍。仿真結果表明延遲降低3.8倍。

5結束語

對交替活躍模式網絡的延遲進行建模，給出延遲的分布函數和平均延遲的計算方法，為節點調度策略提供理論依據和方法指導。采用了主動調度和被動調度兩種節點調度方法對休眠—活躍時間表進行動態調整，降低了端到端延遲。理論分析和仿真結果表明，本文提出的節點調度方法能夠有效適應交替活躍工作模式的部分連接網絡，能夠顯著改善網絡的延遲時間，并能隨應用需求的變化自動選擇最佳的交替活躍模式和路由方式，具有良好的適應性和實用性。

參考文獻：

［1］SHIH E，CHO S H，ICKES N，et al.Physical layer driven protocol and algorithm design for energy－efficient wireless sensor networks[C]//ACM MOBICOM.[S.l.]:[s.n.]，2001:272－287.

[2]FEENEY L M.An energy－consumption model for performance analysis of routing protocols for mobile Ad hoc networks[J].Mobile Networks and Applications，2001，3(6):239－249.

[3]FEENEY L，NILSSON M. Investigating the energy consumption of a wireless network interface in an Ad hoc networking environment[C]//Proc of IEEE INFORCOM.Anchorage， AK:[s.n.]， 2001.

[4]DAS B，BHARGHAVAN V. Routing in Ad hoc networks using minimum connected dominating sets[C]//IEEE International Coference on ICC.[S.l.]:[s.n.]，1997:376－380.

[5]CHEN Benjie，JAMIESON K，BALAKRISHNAN H，et al.Span:an energy－efficient coordination algorithm for topology maintenance in Ad hoc wireless networks [J].ACM Wireless Networks Journal，2002，8(5):481－494.

[6]XU Ya， HEIDEMANN J，ESTRIN D.Adaptive energy－conserving routing for multihop Ad hoc networks，Research Report 527[R].[S.l.]:USC/Information Sciences Institute，2000.

[7]RAMANATHAN R，ROSALES－HAIN R.Topology control of multihop wireless networks using transmit power adjustment[C]//Proc of the IEEE Conference on Computer Communications (INFOCOM).Tel Aviv，Israel:[s.n.]，2000:404－413.

[8]SCHURGERS C， TSIATSIS V， GANERIWAL S，et al.Topology ma－nagement for sensor networks[C]//ACM MOBIHOC.[S.l.]:[s.n.]，2002:135－145.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”