交替活躍的部分連接網(wǎng)絡(luò)休眠調(diào)度策略研究

摘要：提出基于交替活躍的部分連接網(wǎng)絡(luò)的休眠調(diào)度策略，無(wú)須進(jìn)行拓?fù)淇刂疲С州^高的休眠/活躍比率，顯著提高了網(wǎng)絡(luò)平均壽命。給出了滿足延遲要求的休眠時(shí)間表的確定方法。提出簇內(nèi)休眠相位同步和簇間相位次序調(diào)整的主動(dòng)調(diào)節(jié)方法。仿真表明，該方法顯著降低了端到端的延遲。

關(guān)鍵詞：部分連接網(wǎng)絡(luò)；休眠調(diào)度；延遲；仿真

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

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

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

最直接的節(jié)省通信功耗的方法就是對(duì)節(jié)點(diǎn)的通信狀態(tài)進(jìn)行調(diào)度。由于無(wú)線Ad hoc網(wǎng)絡(luò)中，發(fā)送、接收和偵聽(tīng)消耗的功耗相差不大，只有徹底關(guān)閉無(wú)線收發(fā)電路，才具有較好的節(jié)能效果。通過(guò)節(jié)點(diǎn)調(diào)度，讓節(jié)點(diǎn)交替地處于活躍和休眠狀態(tài)的交替活躍模式是節(jié)能的有效方法。但是較低的活躍程度會(huì)造成丟包和響應(yīng)速度降低，甚至成為非連通的網(wǎng)絡(luò)。

由于目前大多數(shù)的Ad hoc路由基于完全連接的拓?fù)浼僭O(shè)，當(dāng)網(wǎng)絡(luò)是非連通時(shí)無(wú)法工作。為避免節(jié)點(diǎn)交替活躍造成的連通性破壞，同時(shí)避免部分節(jié)點(diǎn)能量過(guò)度支出，休眠調(diào)度時(shí)，需要進(jìn)行拓?fù)淇刂啤９?jié)能協(xié)同技術(shù)是一種有效的節(jié)點(diǎn)調(diào)度方法，堅(jiān)持完全連接的假設(shè)，構(gòu)造連通支配集。其中的節(jié)點(diǎn)保持活躍，形成完全連接的骨干網(wǎng)。但是，為了保證網(wǎng)絡(luò)的完全連接，休眠節(jié)點(diǎn)的數(shù)量和休眠時(shí)間均受到限制，影響了節(jié)能效果，而且拓?fù)淇刂频乃惴ㄒ矔?huì)造成額外開(kāi)銷。

另外一種可行的方法就是拋棄完全連接的假設(shè)，節(jié)點(diǎn)按照獨(dú)立的休眠—活躍時(shí)間表進(jìn)行交替切換，所有節(jié)點(diǎn)可以得到公平的休眠機(jī)會(huì)。其控制簡(jiǎn)單，節(jié)省了調(diào)度的能量消耗。同時(shí)，由于不需要保證網(wǎng)絡(luò)的完全連接，允許更多的休眠節(jié)點(diǎn)數(shù)量和更長(zhǎng)的休眠時(shí)間，網(wǎng)絡(luò)整體的壽命得到延長(zhǎng)。但是大量的節(jié)點(diǎn)隨機(jī)地處于交替活躍模式，會(huì)使網(wǎng)絡(luò)的連通性無(wú)法保證，成為部分連接的網(wǎng)絡(luò)。為此，本文提出能夠適應(yīng)部分連接的網(wǎng)絡(luò)異步路由轉(zhuǎn)發(fā)方式。當(dāng)下一跳休眠時(shí)，包會(huì)在本節(jié)點(diǎn)延遲等待；當(dāng)下一跳恢復(fù)活躍時(shí)，繼續(xù)轉(zhuǎn)發(fā)。在連通性無(wú)法保證的部分連接網(wǎng)絡(luò)中，也能維持系統(tǒng)的性能。該方法雖然引入了一定的延遲，但是由于無(wú)須拓?fù)淇刂疲试S更高程度節(jié)點(diǎn)休眠，適用于強(qiáng)調(diào)節(jié)能而對(duì)實(shí)時(shí)性要求不高的領(lǐng)域，如土壤監(jiān)測(cè)、生態(tài)監(jiān)測(cè)、氣象監(jiān)測(cè)等非實(shí)時(shí)的應(yīng)用。

1相關(guān)研究

能量問(wèn)題是無(wú)線Ad hoc關(guān)心的重要問(wèn)題。降低通信功耗是主要途徑。目前對(duì)于通信產(chǎn)生的功耗分析的研究中，建立了很多無(wú)線通信的能量模型。節(jié)點(diǎn)在不同狀態(tài)下的能量消耗具有差異。文獻(xiàn)[2]給出了傳感器網(wǎng)絡(luò)射頻電路RFM的功耗模型，接收、發(fā)送和空閑的功率在9~12 mW，休眠消耗功率僅為0.016 mW。文獻(xiàn)[3]給出了802.11無(wú)線網(wǎng)卡的功耗模型，接收、發(fā)送和空閑的消耗功率分別為1 000 mW、1 400 mW、830 mW，休眠狀態(tài)的功率為130 mW。可見(jiàn)，即使在空閑狀態(tài)，能量的消耗也相當(dāng)大。有效控制通信能量開(kāi)銷就是要讓盡量多的節(jié)點(diǎn)在盡可能多的時(shí)間內(nèi)處于休眠狀態(tài)。

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

另外一種休眠方式就是每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)活躍—休眠時(shí)間表，所有節(jié)點(diǎn)都均等地進(jìn)行自主休眠。AFECA方法[6]采用節(jié)點(diǎn)隨機(jī)休眠的策略，休眠時(shí)間與鄰居節(jié)點(diǎn)的數(shù)量呈正相關(guān)。Stemm和Katz提出了利用應(yīng)用層的指示信息確定節(jié)點(diǎn)的時(shí)間表[7]。但是自主的分布式休眠調(diào)度會(huì)使網(wǎng)絡(luò)的連通性被破壞，對(duì)于需要完全連接拓?fù)涞耐椒绞铰酚墒鞘植焕摹amanathan和Rosales－Hain等人提出調(diào)節(jié)發(fā)送功率的方法維持連通性[7]，拓?fù)淇刂扑惴〞?huì)受到網(wǎng)絡(luò)的支持限制。而文獻(xiàn)[8]則放棄了完全連接的假設(shè)，讓更多的節(jié)點(diǎn)休眠，不需要維持網(wǎng)絡(luò)的連通性；雖然能夠顯著降低能量開(kāi)銷，但是會(huì)造成延遲的增加。

采用延遲轉(zhuǎn)發(fā)的異步方式進(jìn)行通信，不對(duì)網(wǎng)絡(luò)的連通性有要求，無(wú)須拓?fù)淇刂疲试S更多節(jié)點(diǎn)休眠，延長(zhǎng)了網(wǎng)絡(luò)壽命。對(duì)異步通信方式的延遲進(jìn)行估計(jì)，依據(jù)計(jì)算結(jié)果，設(shè)計(jì)了主動(dòng)和被動(dòng)方式的休眠調(diào)度算法，顯著降低了延遲。

2交替活躍網(wǎng)絡(luò)延遲估計(jì)

根據(jù)端到端的延遲分布函數(shù)，可以估計(jì)在容忍的延遲時(shí)間內(nèi)獲得的包遞交率，也可以按照應(yīng)用的遞交率的性能需求，推算延遲等待的時(shí)間；根據(jù)端到端的平均延遲的計(jì)算可以得到節(jié)點(diǎn)按照當(dāng)前休眠時(shí)間表進(jìn)行調(diào)度，也可以獲得系統(tǒng)的響應(yīng)時(shí)間。這兩個(gè)計(jì)算結(jié)果對(duì)強(qiáng)調(diào)節(jié)能休眠的Ad hoc網(wǎng)絡(luò)的節(jié)點(diǎn)調(diào)度具有參考意義和指導(dǎo)作用，也是本文休眠調(diào)度方法的理論依據(jù)。

3休眠—活躍調(diào)度的方法

與協(xié)同調(diào)度方法不同的是，在交替活躍網(wǎng)絡(luò)中不需要拓?fù)淇刂谱尰钴S節(jié)點(diǎn)構(gòu)成路由骨干網(wǎng)，而是讓節(jié)點(diǎn)平等地按照各自的時(shí)間表進(jìn)行休眠—活躍的交替。休眠活躍調(diào)度的主要問(wèn)題就是確定和調(diào)整節(jié)點(diǎn)的時(shí)間表。

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

通過(guò)分簇算法將網(wǎng)絡(luò)分為若干鄰接區(qū)域；簇首領(lǐng)周期性地廣播時(shí)間表以同步區(qū)域內(nèi)部節(jié)點(diǎn)的時(shí)間表。其中包含一個(gè)簇首領(lǐng)時(shí)間戳，表示其已經(jīng)保持活躍的時(shí)間。簇內(nèi)節(jié)點(diǎn)收到后，會(huì)根據(jù)自己已經(jīng)活躍的時(shí)間與該時(shí)間戳進(jìn)行比較，并使具有相同的活躍交替相位。簇內(nèi)時(shí)間表同步可以使節(jié)點(diǎn)同時(shí)活躍的概率增加。

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

被動(dòng)調(diào)度方式的調(diào)節(jié)方法目的是使網(wǎng)絡(luò)在不同情況下呈現(xiàn)不同的活躍特性。網(wǎng)絡(luò)的應(yīng)用層對(duì)響應(yīng)的需求會(huì)隨時(shí)變化（如平時(shí)和戰(zhàn)時(shí)區(qū)別、通常時(shí)期和應(yīng)急時(shí)期的區(qū)別），節(jié)點(diǎn)的休眠表需要進(jìn)行相應(yīng)的調(diào)整。例如在應(yīng)急情況時(shí)，網(wǎng)絡(luò)需要具有較好的響應(yīng)速度，網(wǎng)絡(luò)節(jié)點(diǎn)的活躍程度應(yīng)當(dāng)提高；而對(duì)于平時(shí)情況，網(wǎng)絡(luò)可以延長(zhǎng)休眠。當(dāng)應(yīng)用層對(duì)于性能和響應(yīng)時(shí)間的需求發(fā)生變化，被動(dòng)調(diào)節(jié)方法可以動(dòng)態(tài)修改節(jié)點(diǎn)休眠—活躍時(shí)間表，以調(diào)節(jié)網(wǎng)絡(luò)性能和時(shí)間特性。根據(jù)第2章的計(jì)算結(jié)果，可以通過(guò)調(diào)節(jié)μ和λ達(dá)到調(diào)節(jié)延遲時(shí)間和遞交率的目的。另外，被動(dòng)調(diào)度還包括依據(jù)應(yīng)用對(duì)網(wǎng)絡(luò)的延遲時(shí)間要求，在同步轉(zhuǎn)發(fā)方式和異步轉(zhuǎn)發(fā)方式之間動(dòng)態(tài)選擇。當(dāng)應(yīng)用需要較高實(shí)時(shí)性時(shí)，節(jié)點(diǎn)根據(jù)延遲計(jì)算得到較高的μ。這時(shí)，會(huì)觸發(fā)被動(dòng)調(diào)度過(guò)程，選擇同步轉(zhuǎn)發(fā)方式；反之，采用異步轉(zhuǎn)發(fā)方式。

4仿真和結(jié)果分析

在仿真中，考察場(chǎng)景：100個(gè)節(jié)點(diǎn)隨機(jī)拋撒均勻分布于10 km×10 km的平面區(qū)域，所有節(jié)點(diǎn)均按照交替活躍模型以間歇性方式工作。ON和OFF狀態(tài)到達(dá)時(shí)間間隔服從負(fù)指數(shù)分布，參數(shù)分別為μ=1/10和λ=1/100。位于區(qū)域上方的源節(jié)點(diǎn)node_0~node_5的應(yīng)用層的CBR業(yè)務(wù)源，分別向位于區(qū)域下方的node_94~node_99發(fā)送數(shù)據(jù)包，發(fā)送速率為2 packet/s，包到達(dá)容忍延遲時(shí)間為T，發(fā)包持續(xù)時(shí)間為2 h，平均包長(zhǎng)度500 Bytes，平均路徑長(zhǎng)度為13跳。

當(dāng)所有節(jié)點(diǎn)按初始化的時(shí)間表進(jìn)行交替活躍的工作，平均延遲為12.11 s（計(jì)算估計(jì)值為11.82 s）。當(dāng)進(jìn)行簇劃分（簇直徑為2跳），平均每條路徑經(jīng)過(guò)5.5個(gè)簇，經(jīng)過(guò)簇內(nèi)調(diào)節(jié)后，平均路徑長(zhǎng)度降低為5.5跳。根據(jù)計(jì)算模型得知，平均延遲計(jì)算估計(jì)值為5 s，仿真結(jié)果如圖3所示。穩(wěn)態(tài)后平均為5.2 s。當(dāng)啟動(dòng)簇間調(diào)節(jié)過(guò)程后，理論延遲k降低5.5倍。仿真結(jié)果表明延遲降低3.8倍。

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［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.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”