劉韜，李天瑞，談文蓉，殷鋒

（1. 西南民族大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 成都 610041；2. 西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)(WSN)中，數(shù)據(jù)匯聚是指將不同源節(jié)點(diǎn)的數(shù)據(jù)收集到匯聚節(jié)點(diǎn)（sink），顯然，數(shù)據(jù)（信息）匯聚是無(wú)線傳感器網(wǎng)絡(luò)典型的傳輸形態(tài)[1]。根據(jù)數(shù)據(jù)匯報(bào)方式，無(wú)線傳感器網(wǎng)絡(luò)大致可以分為事件驅(qū)動(dòng)型和周期匯報(bào)型2類網(wǎng)絡(luò)[2]。在事件驅(qū)動(dòng)型傳感器網(wǎng)絡(luò)，節(jié)點(diǎn)平時(shí)很少產(chǎn)生數(shù)據(jù)，僅在待監(jiān)測(cè)的事件發(fā)生時(shí)才產(chǎn)生事件報(bào)告；而在周期匯報(bào)型傳感器網(wǎng)絡(luò)中，所有節(jié)點(diǎn)周期性地向匯聚節(jié)點(diǎn)報(bào)告采集到的信息，直到網(wǎng)絡(luò)生命周期結(jié)束。與事件驅(qū)動(dòng)型網(wǎng)絡(luò)相比，周期匯報(bào)型網(wǎng)絡(luò)中對(duì)節(jié)點(diǎn)匯報(bào)信息實(shí)時(shí)性要求往往較低，但每個(gè)節(jié)點(diǎn)都需要向匯聚節(jié)點(diǎn)周期性地發(fā)送信息，網(wǎng)絡(luò)的數(shù)據(jù)量大，節(jié)點(diǎn)能耗高，且節(jié)點(diǎn)的無(wú)線信號(hào)沖突概率高，節(jié)點(diǎn)之間的無(wú)線信號(hào)相互干擾，MAC層設(shè)計(jì)復(fù)雜。

本文針對(duì)這些難點(diǎn)，提出了一種適用于周期匯報(bào)型網(wǎng)絡(luò)的數(shù)據(jù)匯聚機(jī)制(DDSM)。該機(jī)制在“梯度匯聚”模型的基礎(chǔ)上，聯(lián)合優(yōu)化MAC層和網(wǎng)絡(luò)層功能，采用節(jié)點(diǎn)周期性睡眠/工作的節(jié)能調(diào)度方法，分布式地建立每個(gè)節(jié)點(diǎn)的優(yōu)化路由及工作時(shí)隙。本文的主要貢獻(xiàn)在于以下幾點(diǎn)。

1) 提出一種完全分布式的由各個(gè)節(jié)點(diǎn)自行確立優(yōu)化路由和工作時(shí)隙的機(jī)制，使該機(jī)制具有很強(qiáng)的實(shí)用性，并且采用該機(jī)制的網(wǎng)絡(luò)具有良好的可擴(kuò)展性和可維護(hù)性。

2) MAC層采用分布式TDMA的機(jī)制，并采用聯(lián)合優(yōu)化的思想，融合網(wǎng)絡(luò)層、MAC層，使節(jié)點(diǎn)優(yōu)化路由的建立、發(fā)送時(shí)隙的分配以及節(jié)點(diǎn)的時(shí)鐘同步在一個(gè)過(guò)程中完成，放棄了單層優(yōu)化、各層獨(dú)立設(shè)計(jì)的手段，顯然具有更高的效率，且節(jié)約了能量。

3) 由于節(jié)點(diǎn)間的相互干擾，節(jié)點(diǎn)發(fā)送時(shí)隙的確立是一個(gè)難題。DDSM采用RTS/Final_RTS/CTS的辦法來(lái)解決該問(wèn)題，即通過(guò)多次向鄰居節(jié)點(diǎn)廣播試探性RTS消息，直至沒(méi)有收到否定應(yīng)答幀NAK來(lái)確定發(fā)送時(shí)隙。

2 相關(guān)工作

不同于傳統(tǒng)網(wǎng)絡(luò)協(xié)議棧的層次結(jié)構(gòu)，無(wú)線傳感器網(wǎng)絡(luò)的協(xié)議棧一般被分為4層[3]:應(yīng)用層、網(wǎng)絡(luò)層、媒體介質(zhì)訪問(wèn)控制（MAC，medium access control）層和物理層。近年來(lái)，研究人員提出了許多數(shù)據(jù)收集協(xié)議，例如:網(wǎng)絡(luò)層上，LEACH[4]是比較有代表性的分簇路由算法，而朱紅松等提出了一種精細(xì)化梯度的數(shù)據(jù)匯聚機(jī)制 FGS[1]；MAC層上，經(jīng)典的S-MAC[5]協(xié)議通過(guò)采用周期性偵聽(tīng)/睡眠工作方式來(lái)減少空閑偵聽(tīng)；文獻(xiàn)[6]提出了一種由發(fā)送節(jié)點(diǎn)發(fā)起建立連接的異步低占空比、低碰撞的PB-MAC協(xié)議算法。這些網(wǎng)絡(luò)協(xié)議大都采用單層優(yōu)化的方案，各層相互獨(dú)立。這種單層優(yōu)化的方法雖然給網(wǎng)絡(luò)協(xié)議的模塊化帶來(lái)了方便，但各層之間的相互獨(dú)立、不能協(xié)作，導(dǎo)致網(wǎng)絡(luò)的整體性能不能達(dá)到最優(yōu)[2]。

聯(lián)合優(yōu)化設(shè)計(jì)的方法是近幾年來(lái)提出的主要用于無(wú)線網(wǎng)絡(luò)的設(shè)計(jì)方法，其設(shè)計(jì)思路是融合網(wǎng)絡(luò)層、MAC層和物理層設(shè)計(jì)網(wǎng)絡(luò)協(xié)議，多個(gè)層綜合考慮優(yōu)化，打破層與層之間的獨(dú)立性，從全局的角度對(duì)系統(tǒng)的資源進(jìn)行整合，能最大程度地節(jié)約節(jié)點(diǎn)的能量[7]。王辛果等在文獻(xiàn)[2]中提出一種時(shí)延受限且能量高效的跨層路由協(xié)議，該協(xié)議在做出路由決定時(shí)考慮MAC層的相關(guān)信息。但該協(xié)議為事件驅(qū)動(dòng)型網(wǎng)絡(luò)而設(shè)計(jì)，在設(shè)計(jì)中較少考慮節(jié)點(diǎn)間信號(hào)的沖突和干擾問(wèn)題，顯然不適用于周期匯報(bào)型網(wǎng)絡(luò)。李方敏等基于跨層優(yōu)化的策略提出了一種易于實(shí)現(xiàn)能動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)變化的能量有效的鏈路穩(wěn)定成簇算法[8]，但該算法沒(méi)有分析簇頭到匯聚節(jié)點(diǎn)的優(yōu)化路由，且沒(méi)有考慮信號(hào)沖突問(wèn)題。文獻(xiàn)[9]結(jié)合MAC層協(xié)議與網(wǎng)絡(luò)層路由協(xié)議，提出了AIMRP協(xié)議。該協(xié)議根據(jù)節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù)，形成一個(gè)以匯聚節(jié)點(diǎn)為中心的多層環(huán)形結(jié)構(gòu)，數(shù)據(jù)信息從外環(huán)逐環(huán)向內(nèi)環(huán)傳遞。AIMRP協(xié)議同步精度要求高，但動(dòng)態(tài)適應(yīng)性差，只適用于小范圍的事件驅(qū)動(dòng)型傳感器網(wǎng)絡(luò)。

文獻(xiàn)[10]提出了一種基于TDMA調(diào)度策略的跨層設(shè)計(jì)方案，該方案采用了分簇的結(jié)構(gòu)，并通過(guò)構(gòu)建涉及網(wǎng)絡(luò)層、MAC層和物理層的跨層優(yōu)化模型來(lái)獲得高能效的調(diào)度方案。該方案證明了傳感網(wǎng)的MAC層上采用TDMA機(jī)制具有零沖突、高能效的特點(diǎn)。但該方案是一種集中式的優(yōu)化方案，即由匯聚節(jié)點(diǎn)集中計(jì)算每個(gè)節(jié)點(diǎn)的路由或調(diào)度方案，再把優(yōu)化路由或調(diào)度方案發(fā)送給每個(gè)節(jié)點(diǎn)。集中式的算法缺乏可擴(kuò)展性，網(wǎng)絡(luò)也不具備可伸縮性[11]且匯聚節(jié)點(diǎn)收集源節(jié)點(diǎn)自身信息和發(fā)布優(yōu)化方案的過(guò)程中會(huì)消耗大量能量。

文獻(xiàn)[12]提出了一個(gè)基于TDMA機(jī)制的跨層優(yōu)化數(shù)據(jù)收集協(xié)議 LEEMA，建立以匯聚節(jié)點(diǎn)為根的路由樹(shù)，再通過(guò)該路由樹(shù)為節(jié)點(diǎn)分配工作時(shí)隙。LEEMA采用的是最小跳數(shù)路由，該路由雖然建立簡(jiǎn)單，但是不一定是最小能耗路由，其節(jié)能效果不一定最優(yōu)。另外，LEEMA沒(méi)有考慮負(fù)載均衡，容易形成能量空洞。

盡管在近幾年來(lái)，對(duì)無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)匯聚機(jī)制已經(jīng)有了相當(dāng)?shù)难芯砍晒?，但大都或多或少地存在一些缺陷與不足。本文在此基礎(chǔ)上展開(kāi)研究，在網(wǎng)絡(luò)層和 MAC層上進(jìn)行聯(lián)合優(yōu)化，提出了一個(gè)完全分布式、高能效與低成本的數(shù)據(jù)匯聚機(jī)制。

3 系統(tǒng)模型

3.1 網(wǎng)絡(luò)模型

與文獻(xiàn)[1]和文獻(xiàn)[9]類似，本文中的傳感器網(wǎng)絡(luò)采用“梯度匯聚”模型將節(jié)點(diǎn)的數(shù)據(jù)傳遞給匯聚節(jié)點(diǎn)。假設(shè)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)均勻分布于監(jiān)控區(qū)域中，sink位于區(qū)域中心，節(jié)點(diǎn)密度為p。所有的節(jié)點(diǎn)具有相同的最大無(wú)線傳輸距離R。網(wǎng)絡(luò)被劃分為以sink為圓心的n個(gè)相鄰的環(huán)狀區(qū)域，也稱為“梯度”，d為每個(gè)圓環(huán)的寬度，所有節(jié)點(diǎn)位于各圓環(huán)內(nèi)。從圓心向外，各圓環(huán)依次表示為C1，C2，…，Cn，如圖1所示。

圖1 網(wǎng)絡(luò)模型(n=3)

針對(duì)周期匯報(bào)型傳感器網(wǎng)絡(luò)的特點(diǎn)，做如下說(shuō)明。

1) 網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)周期性的采集和發(fā)送數(shù)據(jù)。每個(gè)工作周期，每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)固定大小的感應(yīng)數(shù)據(jù)分組發(fā)往匯聚節(jié)點(diǎn)。

2) 節(jié)點(diǎn)路由采用“梯度匯聚”模型，處于圓環(huán)(梯度)Ci中的節(jié)點(diǎn)只能選擇圓環(huán)Ci-1中的節(jié)點(diǎn)作為下一跳的數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)(1

3) 所有節(jié)點(diǎn)能夠動(dòng)態(tài)的調(diào)整其發(fā)射功率，例如，Berkeley Motes 節(jié)點(diǎn)就具有100個(gè)發(fā)射功率等級(jí)[13]。

4) 所有節(jié)點(diǎn)的時(shí)鐘能夠保持同步。

為了增加網(wǎng)絡(luò)的連通性，使

另外，經(jīng)信道衰減，無(wú)線信號(hào)最終能否被成功接收取決于接收端的信號(hào)與干擾、噪聲功率比SINR[2]。于是，采用式(2)來(lái)判斷目的節(jié)點(diǎn)能否正確接收無(wú)線信號(hào)

其中，S表示信號(hào)接收功率，W表示噪聲功率，I表示干擾信號(hào)功率。SINRthreshold表示一個(gè)門限值，通常它的值被設(shè)為10。假設(shè)噪聲很小，忽略接收端的噪聲功率，并假設(shè)B為接收節(jié)點(diǎn)，T為干擾節(jié)點(diǎn)的集合，可得

其中，Pr(B)與Pt(X)分別為接收節(jié)點(diǎn)B的接收信號(hào)功率和節(jié)點(diǎn)X的發(fā)送功率，d(X,B)為節(jié)點(diǎn)X與B的距離。

3.2 傳播模型

根據(jù)文獻(xiàn)[14]，當(dāng)節(jié)點(diǎn)A發(fā)送無(wú)線信號(hào)到節(jié)點(diǎn)B時(shí)，節(jié)點(diǎn)B的接收信號(hào)功率Pr(B)為

其中，Pt(A)是節(jié)點(diǎn)A的發(fā)射功率，d(A,B)表示節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的距離。本文假設(shè)傳感器網(wǎng)絡(luò)位于自由空間，則β=2。并且

其中，Gt和Gr分別是發(fā)射天線增益和接收天線增益，λ是信號(hào)波長(zhǎng)。

3.3 相關(guān)定義

定義 1TRCS：載波監(jiān)聽(tīng)門限或感應(yīng)靈敏度。當(dāng)節(jié)點(diǎn)接收信號(hào)功率大于等于TRCS時(shí)，節(jié)點(diǎn)才能感應(yīng)到有信號(hào)發(fā)送。

定義 2TRRX：信號(hào)接收門限。當(dāng)節(jié)點(diǎn)接收信號(hào)功率大于等于TRRX時(shí)，節(jié)點(diǎn)才能正確接收信號(hào)。

定義3RCS：載波最大監(jiān)聽(tīng)距離。當(dāng)節(jié)點(diǎn)以最大發(fā)射功率PtMax發(fā)射信號(hào)時(shí)，另一節(jié)點(diǎn)能感應(yīng)到此次發(fā)送的最遠(yuǎn)距離。根據(jù)式(4)可得

其中，β=2。

定義4R：最大無(wú)線傳輸距離。當(dāng)節(jié)點(diǎn)以最大發(fā)射功率PtMax發(fā)射信號(hào)時(shí)，另一節(jié)點(diǎn)能正確接收此次發(fā)送的最遠(yuǎn)距離。根據(jù)式(4)可得

4 若干關(guān)鍵問(wèn)題

4.1 隱藏節(jié)點(diǎn)問(wèn)題

目前，網(wǎng)絡(luò)通常采用 RTS/CTS(請(qǐng)求發(fā)送/允許發(fā)送)協(xié)議來(lái)解決“隱藏節(jié)點(diǎn)”的問(wèn)題[15]。如圖 2所示，節(jié)點(diǎn)A欲向節(jié)點(diǎn)B發(fā)送數(shù)據(jù)，則：首先，A向B發(fā)送RTS信號(hào)，B收到RTS后，發(fā)CTS信號(hào)，表明已準(zhǔn)備就緒，A可以發(fā)送，而其余收到CTS的節(jié)點(diǎn)則暫停發(fā)送。此協(xié)議認(rèn)為節(jié)點(diǎn)發(fā)送CTS的范圍能夠覆蓋所有的隱藏節(jié)點(diǎn)，但在實(shí)際節(jié)點(diǎn)接收模型中，隱藏節(jié)點(diǎn)的分布范圍遠(yuǎn)大于節(jié)點(diǎn)的發(fā)送范圍[15]。如圖 2所示，若每個(gè)節(jié)點(diǎn)能以最大發(fā)送功率發(fā)送無(wú)線數(shù)據(jù)信號(hào)，則節(jié)點(diǎn)B的干擾節(jié)點(diǎn)區(qū)域是以節(jié)點(diǎn)B的圓心，RCS為半徑的圓，位于此圓內(nèi)的節(jié)點(diǎn)發(fā)送信號(hào)都會(huì)對(duì)節(jié)點(diǎn)B的接收造成干擾。很明顯，節(jié)點(diǎn)B發(fā)CTS信號(hào)，最大發(fā)送功率為，只有與B的距離小于R的節(jié)點(diǎn)才能收到CTS信號(hào)，位于圖2中陰影區(qū)域內(nèi)的節(jié)點(diǎn)無(wú)法收到CTS信號(hào)，而這些節(jié)點(diǎn)又處于節(jié)點(diǎn)B的干擾節(jié)點(diǎn)區(qū)域內(nèi)，若它們此時(shí)發(fā)送數(shù)據(jù)，會(huì)對(duì)節(jié)點(diǎn)B的接收造成干擾，甚至影響接收，形成“隱藏節(jié)點(diǎn)”。這說(shuō)明RTS/CTS協(xié)議在較低信噪比要求的情況下可以防止大部分隱藏節(jié)點(diǎn)，但是隨著信噪比要求的逐步提高，網(wǎng)絡(luò)中的隱藏節(jié)點(diǎn)分布范圍急劇增大，RTS／CTS協(xié)議防止隱藏節(jié)點(diǎn)的效率也隨之降低[15]。

圖2 RTS/CTS握手協(xié)議中的隱藏節(jié)點(diǎn)問(wèn)題

為解決這一問(wèn)題，本文借鑒文獻(xiàn)[16]的方法來(lái)改進(jìn)RTS/CTS協(xié)議，即減小節(jié)點(diǎn)發(fā)送感應(yīng)數(shù)據(jù)的最大發(fā)送功率，從而減小接收節(jié)點(diǎn)的干擾節(jié)點(diǎn)區(qū)域，確保接收節(jié)點(diǎn)以最大發(fā)送功率發(fā)送CTS信號(hào)時(shí)，干擾節(jié)點(diǎn)區(qū)域內(nèi)的節(jié)點(diǎn)都能夠接收到 CTS信號(hào)。假設(shè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)的最大發(fā)送功率限定為為了確保接收節(jié)點(diǎn)的干擾節(jié)點(diǎn)區(qū)域內(nèi)的節(jié)點(diǎn)都能收到來(lái)自接收節(jié)點(diǎn)的CTS信號(hào)，干擾節(jié)點(diǎn)區(qū)域的最大半徑只能為R，根據(jù)式(4)可得

其中，β=2。結(jié)合式(7)可得

所以，為了避免“隱藏節(jié)點(diǎn)”的問(wèn)題，“梯度匯聚”模型中每層圓環(huán)的寬度d重新調(diào)整為

4.2 “梯度匯聚”機(jī)制下的最小能耗路由

“梯度匯聚”機(jī)制下，節(jié)點(diǎn)只能將數(shù)據(jù)傳遞給相鄰環(huán)(梯度)中的節(jié)點(diǎn)。例如，如圖 3所示，節(jié)點(diǎn)D有2條路由到達(dá)sink，分別為D→B→A→sink和D→C→A→sink，節(jié)點(diǎn)D選擇哪條路由首先要判斷總能耗的大小。

圖3 “梯度匯聚”機(jī)制下的最小能耗路由

假設(shè)Emin(X)表示網(wǎng)絡(luò)中任一節(jié)點(diǎn)X生成一個(gè)感應(yīng)數(shù)據(jù)分組到達(dá)匯聚節(jié)點(diǎn)的最小總能耗，Cos(X,Y)表示一個(gè)數(shù)據(jù)分組從節(jié)點(diǎn)X到達(dá)節(jié)點(diǎn)Y的能耗，則

其中，Pt(X)與Pr(Y)分別表示節(jié)點(diǎn)X發(fā)射功率和節(jié)點(diǎn)Y的接收功率，t表示節(jié)點(diǎn)發(fā)送或接收一個(gè)數(shù)據(jù)分組所花費(fèi)的時(shí)間。為了進(jìn)一步降低節(jié)點(diǎn)的能耗，盡量減小發(fā)送節(jié)點(diǎn)發(fā)送數(shù)據(jù)的功率，當(dāng)接收端的接收信號(hào)功率等于信號(hào)接收門限TRRX時(shí)，結(jié)合式(4)，可以獲得節(jié)點(diǎn)發(fā)送信號(hào)所需的最小發(fā)射功率Ptmin

其中，d(X，Y)表示發(fā)送節(jié)點(diǎn)X與接收節(jié)點(diǎn)Y的距離。根據(jù)式(12)與式(13)，可得一個(gè)數(shù)據(jù)分組從節(jié)點(diǎn)X到達(dá)節(jié)點(diǎn)Y的最小能耗

其中，節(jié)點(diǎn)的接收功率一般為固定值Pr。若Sn為節(jié)點(diǎn)X位于相鄰梯度(相鄰內(nèi)層圓環(huán))的鄰居節(jié)點(diǎn)集合，結(jié)合式(14)，Emin(X)可以通過(guò)式(15)計(jì)算。

如果節(jié)點(diǎn)獲得了它所有相鄰梯度的鄰居節(jié)點(diǎn)生成一個(gè)數(shù)據(jù)分組到達(dá)匯聚節(jié)點(diǎn)的最小總能耗，它就能根據(jù)式(15)計(jì)算得到它相應(yīng)的最小總能耗，并選擇對(duì)應(yīng)的鄰居節(jié)點(diǎn)為下一跳目的節(jié)點(diǎn)。當(dāng)每個(gè)節(jié)點(diǎn)都確立了下一跳目的節(jié)點(diǎn)后，節(jié)點(diǎn)到達(dá)匯聚節(jié)點(diǎn)的優(yōu)化路由自然就確立了。所以，DDSM中，節(jié)點(diǎn)優(yōu)化路由的建立過(guò)程是由內(nèi)而外，逐環(huán)建立的。即先由第1層圓環(huán)的節(jié)點(diǎn)先確立下跳目的節(jié)點(diǎn)，再由第2層圓環(huán)的節(jié)點(diǎn)確立下跳目的節(jié)點(diǎn)，以此類推，直至最外層。這樣做的目的是在內(nèi)層圓環(huán)（梯度）的節(jié)點(diǎn)優(yōu)化路由的建立過(guò)程中，通知外層相鄰圓環(huán)鄰居節(jié)點(diǎn)其優(yōu)化路由等信息。當(dāng)輪到外層相鄰圓環(huán)鄰居節(jié)點(diǎn)建立優(yōu)化路由時(shí)，就可以依據(jù)這些信息，通過(guò)式(15)做出選擇。

另外，節(jié)點(diǎn)選擇其下一跳路由節(jié)點(diǎn)時(shí)，還要注意平衡節(jié)點(diǎn)的負(fù)載，避免把某個(gè)節(jié)點(diǎn)頻繁選作路由中繼節(jié)點(diǎn)，從而過(guò)快耗盡能量造成能量空洞。

5 DDSM機(jī)制描述

TDMA機(jī)制是網(wǎng)絡(luò)無(wú)線信道分配機(jī)制之一，具有零沖突、高能效、低時(shí)延的特點(diǎn)，可以很好地應(yīng)用于數(shù)據(jù)量大的周期匯報(bào)型傳感器網(wǎng)絡(luò)，所以DDSM采用TDMA機(jī)制實(shí)現(xiàn)無(wú)線信道分配。

DDSM按輪運(yùn)行，每輪分為2個(gè)階段。第一階段是節(jié)點(diǎn)優(yōu)化路由和時(shí)隙調(diào)度表的建立階段:每個(gè)節(jié)點(diǎn)分布式地確立自身到匯聚節(jié)點(diǎn)的數(shù)據(jù)發(fā)送路由、所需的發(fā)送功率以及相應(yīng)子階段內(nèi)的工作時(shí)隙；第二階段是節(jié)點(diǎn)數(shù)據(jù)匯聚階段，節(jié)點(diǎn)根據(jù)分配好的工作時(shí)隙，周期性地從休眠狀態(tài)醒來(lái)，發(fā)送數(shù)據(jù)或接收數(shù)據(jù)，數(shù)據(jù)則遵循建立好的優(yōu)化路由，由外而內(nèi)，逐環(huán)(梯度)的方向向匯聚節(jié)點(diǎn)傳遞。每輪都要重新建立每個(gè)節(jié)點(diǎn)的工作時(shí)隙和發(fā)送路由是為了適應(yīng)因個(gè)別節(jié)點(diǎn)位置變化或節(jié)點(diǎn)死亡而造成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化。

5.1 數(shù)據(jù)匯聚階段

每輪的數(shù)據(jù)匯聚階段由若干個(gè)數(shù)據(jù)采集周期組成，所有節(jié)點(diǎn)在每個(gè)數(shù)據(jù)采集周期都要生成一個(gè)感應(yīng)數(shù)據(jù)分組，并向匯聚節(jié)點(diǎn)發(fā)送。為避免沖突，如圖4所示，將一個(gè)數(shù)據(jù)采集周期再劃分為若干子周期，每個(gè)子周期再繼續(xù)劃分為m個(gè)時(shí)隙，單個(gè)時(shí)隙的長(zhǎng)度等于節(jié)點(diǎn)發(fā)送一個(gè)感應(yīng)數(shù)據(jù)分組所需的時(shí)間，m也必須足夠大使節(jié)點(diǎn)能夠有時(shí)間發(fā)送完所有的數(shù)據(jù)分組。每個(gè)子周期分配給一個(gè)圓環(huán)(梯度)，位于圓環(huán)Ci(1＜i≤n)內(nèi)的節(jié)點(diǎn)只能在每個(gè)數(shù)據(jù)采集周期的第n-i+1個(gè)子周期內(nèi)的相應(yīng)時(shí)隙發(fā)送數(shù)據(jù)，而相鄰圓環(huán)梯度的節(jié)點(diǎn)則接收數(shù)據(jù)。例如，第一個(gè)子周期第3層圓環(huán)的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，第2層圓環(huán)的節(jié)點(diǎn)則接收數(shù)據(jù)；而第2個(gè)子周期第2層圓環(huán)的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，第1層圓環(huán)的節(jié)點(diǎn)則接收數(shù)據(jù)，以此類推，直至發(fā)送到匯聚節(jié)點(diǎn)。而節(jié)點(diǎn)在相應(yīng)子周期的發(fā)送時(shí)隙則由 DDSM 在每輪的節(jié)點(diǎn)優(yōu)化路由和時(shí)隙調(diào)度表的建立階段中確立。

圖4 一個(gè)數(shù)據(jù)采集周期的時(shí)間劃分

5.2 節(jié)點(diǎn)優(yōu)化路由和時(shí)隙調(diào)度表的建立階段

DDSM在本階段采用多層次聯(lián)合優(yōu)化的思想，建立“梯度匯聚”機(jī)制下每個(gè)節(jié)點(diǎn)發(fā)往匯聚節(jié)點(diǎn)的優(yōu)化路由，并同時(shí)確立每個(gè)節(jié)點(diǎn)無(wú)沖突的時(shí)隙調(diào)度表。為了避免不同節(jié)點(diǎn)在建立路由和時(shí)隙調(diào)度表的過(guò)程中發(fā)生信號(hào)沖突，所有節(jié)點(diǎn)逐個(gè)輪流建立自己的優(yōu)化路由和時(shí)隙調(diào)度表。因?yàn)閮?yōu)化路由的建立過(guò)程與時(shí)隙建立過(guò)程分別依賴不同方向的累積效應(yīng)，將該階段劃分為2個(gè)子階段：節(jié)點(diǎn)優(yōu)化路由建立子階段和節(jié)點(diǎn)時(shí)隙調(diào)度表的建立子階段。

為了方便節(jié)點(diǎn)建立優(yōu)化路由和時(shí)隙調(diào)度表，每個(gè)節(jié)點(diǎn)都建立了2張表，內(nèi)層圓環(huán)的鄰居節(jié)點(diǎn)信息表和節(jié)點(diǎn)的時(shí)隙情況表，例表分別如表1與表2所示。

表1中存儲(chǔ)的是節(jié)點(diǎn)的相鄰內(nèi)層圓環(huán)中鄰居節(jié)點(diǎn)的信息。其中，NodeID是鄰居節(jié)點(diǎn)的ID，relayed是需要通過(guò)本節(jié)點(diǎn)中繼(轉(zhuǎn)發(fā))數(shù)據(jù)分組的節(jié)點(diǎn)數(shù)量。Emin是節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)分組到達(dá)匯聚節(jié)點(diǎn)過(guò)程中的最小能耗，dist是本節(jié)點(diǎn)到該鄰居節(jié)點(diǎn)的距離。assigned_slots[m]表示節(jié)點(diǎn)在數(shù)據(jù)匯聚階段相應(yīng)的接收子周期內(nèi)時(shí)隙占用情況的數(shù)組，1表示該時(shí)隙已被占用來(lái)接收某節(jié)點(diǎn)信號(hào)，0表示空閑。注意第1層圓環(huán)中節(jié)點(diǎn)的表1只需要記錄匯聚節(jié)點(diǎn)的相關(guān)信息。表2中存儲(chǔ)的是節(jié)點(diǎn)在一個(gè)子周期的每個(gè)時(shí)隙的情況表，包括節(jié)點(diǎn)在相應(yīng)時(shí)隙內(nèi)是否處于接收狀態(tài)receiving(1表示節(jié)點(diǎn)在該時(shí)隙內(nèi)處于接收狀態(tài))和每個(gè)時(shí)隙的累積干擾信號(hào)功率Pinterfere，用于計(jì)算SINR。網(wǎng)絡(luò)初始化時(shí)，2張表為空表。節(jié)點(diǎn)在建立路由和時(shí)隙調(diào)度表的過(guò)程中，不斷完善這2張表。

表1 鄰居節(jié)點(diǎn)信息

表2 節(jié)點(diǎn)時(shí)隙情況

5.2.1 節(jié)點(diǎn)優(yōu)化路由建立子階段

以圖5所示為例，顯示了位于圓環(huán)Ci中的節(jié)點(diǎn)A使用算法1確立下一跳目的節(jié)點(diǎn)的過(guò)程，算法1具體步驟描述如下。

1) 節(jié)點(diǎn)A從表1中挑選負(fù)載（relayed）不超過(guò)τ的相鄰內(nèi)層圓環(huán)中鄰居節(jié)點(diǎn)，即relayed≤τ(τ為節(jié)點(diǎn)允許通過(guò)本節(jié)點(diǎn)轉(zhuǎn)發(fā)的節(jié)點(diǎn)數(shù)量最大門限值，這樣做的目的是均衡同一層圓環(huán)內(nèi)節(jié)點(diǎn)的負(fù)載)，并保存到集合Set中。

2) 若集合Set不為空，則以集合Set中的節(jié)點(diǎn)為A的中繼節(jié)點(diǎn)，結(jié)合表1中的相關(guān)信息，根據(jù)式(15)計(jì)算Emin(A)，并獲得中繼節(jié)點(diǎn)B，確定該鄰居節(jié)點(diǎn)B為下一跳目的節(jié)點(diǎn)，進(jìn)入步驟4)。

3) 若集合Set為空，則τ=2τ，返回步驟1)。

4) 節(jié)點(diǎn)A設(shè)置發(fā)射功率為Ptm，發(fā)送消息RTS，消息中包含下一跳目的節(jié)點(diǎn)B的NodeID、節(jié)點(diǎn)A的梯度值(HC)和最低總能耗Emin(A)。

5) 節(jié)點(diǎn)B收到消息RTS后，修改表1中相應(yīng)內(nèi)容，然后以功率Ptm發(fā)送消息CTS。

6) 若節(jié)點(diǎn)A相鄰?fù)鈱訄A環(huán)中的鄰居節(jié)點(diǎn)收到RTS，如節(jié)點(diǎn)D，則據(jù)無(wú)線信號(hào)強(qiáng)度值RSSI（received signal strength indicator）來(lái)獲得2個(gè)節(jié)點(diǎn)的相對(duì)距離dist，根據(jù)式(4)可得

其中，β=2，Precv為接收端接收到的信號(hào)功率。

然后，節(jié)點(diǎn)D更新其表1中與節(jié)點(diǎn)A對(duì)應(yīng)的相應(yīng)內(nèi)容（Emin，dist等）。

7) 若節(jié)點(diǎn)B相鄰?fù)鈱訄A環(huán)中的鄰居節(jié)點(diǎn)收到CTS，如節(jié)點(diǎn)F，則更新其表1中與節(jié)點(diǎn)B對(duì)應(yīng)的相應(yīng)內(nèi)容（relayed=relayed+1）。

節(jié)點(diǎn)A完成上述RTS/CTS握手過(guò)程后，進(jìn)入休眠狀態(tài)直至節(jié)點(diǎn)時(shí)隙調(diào)度表的建立子階段。

需要注意的是，根據(jù)文獻(xiàn)[17]的論證，不同層內(nèi)節(jié)點(diǎn)的能耗是不可能完全均衡的，所以算法1確保同一層圓環(huán)內(nèi)節(jié)點(diǎn)的負(fù)載均衡。

圖5 RTS/CTS握手過(guò)程

圖6給出網(wǎng)絡(luò)中節(jié)點(diǎn)優(yōu)化路由的建立過(guò)程：首先，由第1層圓環(huán)中的節(jié)點(diǎn)輪流執(zhí)行算法1，但要注意此時(shí)節(jié)點(diǎn)的目的節(jié)點(diǎn)只能是匯聚節(jié)點(diǎn)，并通知第2層圓環(huán)中的節(jié)點(diǎn)更新相關(guān)信息；然后，第2層圓環(huán)中的節(jié)點(diǎn)輪流執(zhí)行算法1，確定其位于第1層圓環(huán)中的下一跳目的節(jié)點(diǎn)，并通知第3層圓環(huán)中的節(jié)點(diǎn)更新相關(guān)信息；接著第3層，…，直至最外層圓環(huán)中節(jié)點(diǎn)完成此路由建立過(guò)程。

5.2.2 節(jié)點(diǎn)時(shí)隙調(diào)度表的建立子階段

在所有節(jié)點(diǎn)均確立了下一跳目的節(jié)點(diǎn)后，網(wǎng)絡(luò)進(jìn)入節(jié)點(diǎn)時(shí)隙調(diào)度表的建立子階段。如圖6所示，該子階段與節(jié)點(diǎn)優(yōu)化路由建立的過(guò)程相反，所有節(jié)點(diǎn)按照由外到內(nèi)的圓環(huán)順序輪流建立時(shí)隙調(diào)度表。即先由最外層圓環(huán)的節(jié)點(diǎn)先輪流確立發(fā)送時(shí)隙，建立時(shí)隙調(diào)度表，再由次外層圓環(huán)的節(jié)點(diǎn)建立時(shí)隙調(diào)度表，…，以此類推，直至第1層圓環(huán)。

圖6 節(jié)點(diǎn)優(yōu)化路由及工作時(shí)隙的建立順序

該子階段中，每個(gè)節(jié)點(diǎn)都需要維持變量load記錄一個(gè)數(shù)據(jù)采集周期內(nèi)自己需要發(fā)送的數(shù)據(jù)分組數(shù)量，包括轉(zhuǎn)發(fā)的數(shù)據(jù)分組和自己生成的數(shù)據(jù)分組，初始值為1。因?yàn)閿?shù)據(jù)匯聚階段中，一個(gè)時(shí)隙的長(zhǎng)度等于節(jié)點(diǎn)發(fā)送一個(gè)感應(yīng)數(shù)據(jù)分組所需的時(shí)間，所以節(jié)點(diǎn)需要的時(shí)隙數(shù)量等于load。節(jié)點(diǎn)在確立一個(gè)發(fā)送時(shí)隙時(shí)，既要判斷目的節(jié)點(diǎn)在此時(shí)隙內(nèi)是否是空閑的，還要判斷此次發(fā)送是否會(huì)影響該時(shí)隙內(nèi)處于接收狀態(tài)的非目的節(jié)點(diǎn)的接收過(guò)程。DDSM 擬采用RTS/Final_RTS/CTS握手的辦法來(lái)解決該問(wèn)題，即通過(guò)多次向鄰居節(jié)點(diǎn)廣播試探性RTS消息，直至沒(méi)有收到否定應(yīng)答幀NAK來(lái)確定發(fā)送時(shí)隙。

位于圓環(huán)Ci(1

1) 節(jié)點(diǎn)A從表1中選擇下一跳目的節(jié)點(diǎn)B的最小空閑時(shí)隙，并根據(jù)式(13)計(jì)算節(jié)點(diǎn)A發(fā)送信號(hào)所需的最小發(fā)射功率，然后以最大發(fā)射功率發(fā)試探性的請(qǐng)求消息RTS，消息中包含欲請(qǐng)求的時(shí)隙號(hào)ReqSlot與的值。

2) 圓環(huán)Ci-1中的節(jié)點(diǎn)(除節(jié)點(diǎn)B)收到該RTS，則判斷自己在節(jié)點(diǎn)A的請(qǐng)求時(shí)隙內(nèi)是否處于接收狀態(tài)，若處于接收狀態(tài)，則將節(jié)點(diǎn)A到節(jié)點(diǎn)B的信號(hào)發(fā)送視為對(duì)自己的干擾，結(jié)合節(jié)點(diǎn)A的發(fā)射功率，并根據(jù)表 2和式(3)計(jì)算SINR，若小于SINRthreshold則發(fā)否定應(yīng)答消息NAK。

3) 目的節(jié)點(diǎn)B收到該RTS后，也根據(jù)表2和式(3)計(jì)算SINR，若小于SINRthreshold則同樣發(fā)否定應(yīng)答消息NAK。

4) 節(jié)點(diǎn)A收到NAK或探測(cè)到有沖突發(fā)生，則說(shuō)明該請(qǐng)求時(shí)隙被否定，重新從鄰居節(jié)點(diǎn)信息表中選擇下一跳目的節(jié)點(diǎn)B次小的空閑時(shí)隙，再次以最大功率PtMax發(fā)試探性的請(qǐng)求消息RTS，返回步驟2。

5) 節(jié)點(diǎn)A發(fā)了RTS后在大小為TimeOut的后續(xù)時(shí)間內(nèi)沒(méi)有收到NAK或探測(cè)到有沖突發(fā)生，說(shuō)明請(qǐng)求成功，節(jié)點(diǎn)A以最大功率PtMax再發(fā)最終的請(qǐng)求消息Final_RTS。

6) 目的節(jié)點(diǎn)B收到消息 Final_RTS后，修改load（load=load+1）及表2中對(duì)應(yīng)時(shí)隙的接收狀態(tài)（receiving），以最大功率PtMax發(fā)送消息CTS；而節(jié)點(diǎn)A在相鄰內(nèi)層圓環(huán)中的其他鄰居節(jié)點(diǎn)收到消息Final_RTS后，修改表2中對(duì)應(yīng)時(shí)隙的累積干擾信號(hào)功率Pinterfere。

7) 節(jié)點(diǎn)B的相鄰?fù)鈱訄A環(huán)中的節(jié)點(diǎn)收到消息CTS后，更新其表1中節(jié)點(diǎn)B對(duì)應(yīng)的空閑時(shí)隙表assigned_slots[m]，把請(qǐng)求時(shí)隙的對(duì)應(yīng)位設(shè)置為1，表示該時(shí)隙已經(jīng)被占用。

因?yàn)橐粋€(gè)時(shí)隙只能發(fā)送一個(gè)數(shù)據(jù)分組，而每個(gè)節(jié)點(diǎn)有l(wèi)oad個(gè)數(shù)據(jù)分組需要發(fā)送，所以節(jié)點(diǎn)重復(fù)執(zhí)行l(wèi)oad次算法2，申請(qǐng)load個(gè)時(shí)隙。

圖7描述了算法2的一次執(zhí)行過(guò)程（節(jié)點(diǎn)I與節(jié)點(diǎn)J位于圓環(huán)Ci-1中，且為A的鄰居節(jié)點(diǎn)）：首先，A發(fā)送請(qǐng)求消息RTS；節(jié)點(diǎn)I收到后，經(jīng)判斷，發(fā)送否定應(yīng)答消息NAK；節(jié)點(diǎn)A收到NAK后，重新選擇請(qǐng)求時(shí)隙，并再次發(fā)送請(qǐng)求消息RTS；節(jié)點(diǎn)J收到后，經(jīng)判斷，再發(fā)否定應(yīng)答消息NAK，…，此過(guò)程一直重復(fù)，直到?jīng)]有收到NAK或探測(cè)到?jīng)_突，于是發(fā)消息Final_RTS確認(rèn)請(qǐng)求時(shí)隙，目的節(jié)點(diǎn)B發(fā)送消息CTS回應(yīng)。

圖7 時(shí)隙請(qǐng)求算法中的消息

當(dāng)?shù)趎層到第2層中的節(jié)點(diǎn)完成時(shí)隙調(diào)度表的建立后，第1層圓環(huán)中的節(jié)點(diǎn)則輪流直接向匯聚節(jié)點(diǎn)發(fā)送請(qǐng)求消息RTS，匯聚節(jié)點(diǎn)回復(fù)消息CTS，包含允許節(jié)點(diǎn)發(fā)送的發(fā)送時(shí)隙。

6 相關(guān)參數(shù)分析

6.1 參數(shù)m分析

DDSM中，參數(shù)m是一個(gè)數(shù)據(jù)采集周期中每個(gè)子周期的時(shí)隙數(shù)量，并且單個(gè)時(shí)隙的長(zhǎng)度等于節(jié)點(diǎn)發(fā)送一個(gè)感應(yīng)數(shù)據(jù)分組所需的時(shí)間。如果m的值過(guò)小，則可能會(huì)造成節(jié)點(diǎn)在其相應(yīng)的發(fā)送子周期中沒(méi)有足夠的時(shí)間發(fā)送完所有的數(shù)據(jù)分組；如果m的值過(guò)大，則會(huì)增加感應(yīng)數(shù)據(jù)傳遞到匯聚節(jié)點(diǎn)的時(shí)延。

由于感應(yīng)數(shù)據(jù)是按梯度逐級(jí)向匯聚節(jié)點(diǎn)傳遞的，每層圓環(huán)的節(jié)點(diǎn)都需要轉(zhuǎn)發(fā)外層圓環(huán)中節(jié)點(diǎn)的感應(yīng)數(shù)據(jù)。很明顯，各層圓環(huán)中節(jié)點(diǎn)所需要發(fā)送的數(shù)據(jù)分組是不相同的，內(nèi)層圓環(huán)中的節(jié)點(diǎn)需要發(fā)送的數(shù)據(jù)分組往往較外層圓環(huán)中節(jié)點(diǎn)的數(shù)據(jù)分組多，也就需要更多的發(fā)送時(shí)隙。特別地，第一層圓環(huán)中的節(jié)點(diǎn)需要發(fā)送網(wǎng)絡(luò)中所有節(jié)點(diǎn)的感應(yīng)數(shù)據(jù)分組，包括轉(zhuǎn)發(fā)的數(shù)據(jù)分組和節(jié)點(diǎn)自身生成的數(shù)據(jù)分組，而且第一層圓環(huán)中的節(jié)點(diǎn)只能將數(shù)據(jù)分組發(fā)送給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)只能逐個(gè)接收每個(gè)節(jié)點(diǎn)的數(shù)據(jù)分組，所以第一層圓環(huán)中的節(jié)點(diǎn)發(fā)送數(shù)據(jù)相應(yīng)的子周期內(nèi)需要最多的時(shí)隙。所以，m應(yīng)當(dāng)滿足

其中，N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，ρ為節(jié)點(diǎn)分布密度，SA為監(jiān)控區(qū)域面積。

6.2 參數(shù)ω分析

如圖8所示，任一節(jié)點(diǎn)Q位于圓環(huán)Ci，與sink的距離為r。深色區(qū)域?yàn)楣?jié)點(diǎn)Q的下一跳可達(dá)區(qū)域，即位于該區(qū)域的節(jié)點(diǎn)才能夠接收節(jié)點(diǎn)Q的數(shù)據(jù)，若該區(qū)域沒(méi)有節(jié)點(diǎn)，則造成該節(jié)點(diǎn)無(wú)法連通，并發(fā)送數(shù)據(jù)。根據(jù)文獻(xiàn)[18]，因節(jié)點(diǎn)均勻分布，所以節(jié)點(diǎn)的部署服從泊松分布，于是，可通過(guò)式(18)計(jì)算該節(jié)點(diǎn)可以連通的概率p。

其中，Sq為節(jié)點(diǎn)下一跳可達(dá)區(qū)域的面積。顯然，p與Sq正相關(guān)。根據(jù)式(11)，ω（0＜ω＜1）的大小決定了圓環(huán)的寬度d。若ω越大，則d越大，網(wǎng)絡(luò)中的圓環(huán)數(shù)量越少，但節(jié)點(diǎn)的可達(dá)區(qū)域（尤其是位于圓環(huán)外邊緣的節(jié)點(diǎn)）的面積越小，網(wǎng)絡(luò)連通性變差；ω變小，節(jié)點(diǎn)的可達(dá)區(qū)域面積增加，網(wǎng)絡(luò)連通性變好，但是d減小造成網(wǎng)絡(luò)中的圓環(huán)數(shù)量增加，網(wǎng)絡(luò)數(shù)據(jù)匯聚的總能耗也隨之增加。所以，在滿足節(jié)點(diǎn)的連通的概率p大于門限值pt的情況下，合理選擇ω的值。要使p＞pt，則根據(jù)式(18)，Sq要滿足

圖8 任意節(jié)點(diǎn)Q的下一跳可達(dá)區(qū)域

若Q位于圓環(huán)Ci的外邊緣上(r=id)，結(jié)合圖8，Sq可通過(guò)式(20)獲得。

顯然，位于圓環(huán)Ci的外邊緣上節(jié)點(diǎn)的Sq小于該圓環(huán)內(nèi)其他節(jié)點(diǎn)的Sq，若位于圓環(huán)Ci的外邊緣上節(jié)點(diǎn)的Sq滿足式（19），則所有節(jié)點(diǎn)的連通性可以得到保證。因網(wǎng)絡(luò)中圓環(huán)數(shù)量有限，采用一種啟發(fā)式算法來(lái)快速獲得該問(wèn)題的近似解，描述如下。

1)ω初值取0.99；

2) 利用式(11)計(jì)算圓環(huán)的寬度d；

3) 利用式(20)計(jì)算每層圓環(huán)的外邊緣節(jié)點(diǎn)的Sq，然后利用式(19)判斷這些節(jié)點(diǎn)的連通的概率p是否大于門限值pt；若均滿足條件，則確定ω的值，并退出；否則ω=ω-Δ(Δ為一較小的數(shù)，如0.1)，返回步驟2)。

7 性能分析

7.1 模擬實(shí)驗(yàn)環(huán)境設(shè)置和參數(shù)

利用 OPNET作為模擬實(shí)驗(yàn)平臺(tái)，對(duì)所提DDSM機(jī)制進(jìn)行評(píng)估和分析。仿真實(shí)驗(yàn)中，所有節(jié)點(diǎn)均勻分布于一個(gè)半徑為L(zhǎng)的圓中，匯聚節(jié)點(diǎn)位于圓心處，且整個(gè)圓被劃分為n個(gè)寬度為d的圓環(huán)。如無(wú)特別指定，所有的實(shí)驗(yàn)參數(shù)設(shè)置如表3所示。

表3 模擬參數(shù)

根據(jù)式(7)和表3中的參數(shù)，可以計(jì)算出節(jié)點(diǎn)的最大無(wú)線傳輸距離R=125 m。正如本文4.1節(jié)所述，為了避免隱藏節(jié)點(diǎn)問(wèn)題，需要減小節(jié)點(diǎn)發(fā)送感應(yīng)數(shù)據(jù)的最大發(fā)送功率，從而減小接收節(jié)點(diǎn)的干擾節(jié)點(diǎn)區(qū)域。于是，節(jié)點(diǎn)發(fā)送感應(yīng)數(shù)據(jù)的最遠(yuǎn)距離由R縮短為rm（式(10)），而每層圓環(huán)的寬度d也隨之調(diào)整（式(11)）。

另外，為了確保網(wǎng)絡(luò)具有很好的連通性，假設(shè)節(jié)點(diǎn)連通的概率門限值pt=0.95，使用6.2節(jié)中的啟發(fā)式算法來(lái)獲取合理的ω值，使所有節(jié)點(diǎn)連通的概率p大于pt，同時(shí)使用式(11)計(jì)算此時(shí)每層圓環(huán)的寬度d。經(jīng)計(jì)算，可得ω=0.6，d=33.5 m。如無(wú)特別值，ω和d分別設(shè)置為0.6和33.5 m。

根據(jù)相應(yīng)的仿真參數(shù)，實(shí)驗(yàn)中所采用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖9所示。其中，匯聚節(jié)點(diǎn)位于圖中心。

圖9 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)（n=3）

7.2 實(shí)驗(yàn)結(jié)果

7.2.1 不同參數(shù)取值對(duì)網(wǎng)絡(luò)性能的影響

根據(jù)式(11)，ω的取值會(huì)改變網(wǎng)絡(luò)中每層圓環(huán)的寬度。首先分析ω的不同取值對(duì)網(wǎng)絡(luò)連通性的影響。

圖10反映了不同ω的取值下，通過(guò)式(18)與式(20)計(jì)算獲得的網(wǎng)絡(luò)中節(jié)點(diǎn)最低連通概率。當(dāng)ω的值越大時(shí)，根據(jù)式(11)，圓環(huán)的寬度也就越大，但是每層圓環(huán)外邊緣的節(jié)點(diǎn)可以選擇的下一跳節(jié)點(diǎn)的范圍也就越小，以至于影響網(wǎng)絡(luò)的連通性。

圖 11反映了不同ω的取值下，網(wǎng)絡(luò)采用DDSM機(jī)制運(yùn)行120 min后節(jié)點(diǎn)數(shù)據(jù)分組的成功到達(dá)率(指到達(dá)匯聚節(jié)點(diǎn))。從圖中可以看出，當(dāng)ω＞0.6時(shí)，數(shù)據(jù)分組的成功到達(dá)率明顯下降，這與分析計(jì)算結(jié)果吻合，說(shuō)明分析正確。后面的實(shí)驗(yàn)中，為保證網(wǎng)絡(luò)的連通性，門限值pt取值0.95，ω則取值0.6。

圖10 不同ω下的節(jié)點(diǎn)最低連通概率（n=3）

圖11 不同ω下的數(shù)據(jù)分組成功到達(dá)率（n=3）

接下來(lái)分析節(jié)點(diǎn)允許轉(zhuǎn)發(fā)的節(jié)點(diǎn)數(shù)量最大門限值τ對(duì)數(shù)據(jù)分組的成功到達(dá)率的影響。當(dāng)τ的取值比較小時(shí)，每個(gè)節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，允許轉(zhuǎn)發(fā)的節(jié)點(diǎn)數(shù)量得到了嚴(yán)格的限制，避免了個(gè)別節(jié)點(diǎn)頻繁被作為中繼節(jié)點(diǎn)，從而過(guò)早地耗盡了能量。但是如果τ的取值過(guò)小，部分節(jié)點(diǎn)可能會(huì)找不到下一跳目的節(jié)點(diǎn)，從而影響了網(wǎng)絡(luò)的連通性。圖 12給出了不同的τ值對(duì)數(shù)據(jù)分組的成功到達(dá)率的影響，從τ=2開(kāi)始，數(shù)據(jù)分組成功到達(dá)率逐漸提高，當(dāng)τ=4時(shí)，數(shù)據(jù)分組成功到達(dá)率達(dá)到了90%。

7.2.2 與其他數(shù)據(jù)收集機(jī)制比較

為了評(píng)估 DDSM 的性能，比較 AIMRP[9]、S-MAC[5]、LEMMA[12]和DDSM這4種數(shù)據(jù)收集協(xié)議在數(shù)據(jù)分組成功到達(dá)率和功耗方面的性能。S-MAC協(xié)議中，假設(shè)節(jié)點(diǎn)采用最小跳路由到達(dá)匯聚節(jié)點(diǎn)。

如圖13所示，在4種數(shù)據(jù)收集協(xié)議都不允許數(shù)據(jù)分組發(fā)送失敗重傳的條件下，比較4種協(xié)議的數(shù)據(jù)分組成功到達(dá)率。從圖 13可以看出，當(dāng)圓環(huán)的數(shù)量增加時(shí)，即網(wǎng)絡(luò)的規(guī)模擴(kuò)大時(shí)，采用AIMRP和S-MAC這2種協(xié)議的數(shù)據(jù)分組成功到達(dá)率不斷下降，而DDSM和LEMMA的數(shù)據(jù)分組成功到達(dá)率則基本維持在90%以上。這是因?yàn)锳IMRP協(xié)議每次發(fā)送數(shù)據(jù)分組都需要通過(guò) RTR/CTR/DATA/ACK握手機(jī)制實(shí)現(xiàn)，過(guò)程繁瑣，動(dòng)態(tài)適應(yīng)性差，只能適用于小范圍的事件驅(qū)動(dòng)型傳感器網(wǎng)絡(luò)。S-MAC協(xié)議采用周期性的偵聽(tīng)/睡眠機(jī)制，其偵聽(tīng)/睡眠時(shí)間不能根據(jù)網(wǎng)絡(luò)中負(fù)載的變化動(dòng)態(tài)調(diào)整，而且 S-MAC協(xié)議采用退避發(fā)送機(jī)制來(lái)降低節(jié)點(diǎn)間碰撞的概率，當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)，網(wǎng)絡(luò)中數(shù)據(jù)量增加，采用 S-MAC協(xié)議網(wǎng)絡(luò)的信道碰撞的幾率急劇增大，易導(dǎo)致網(wǎng)絡(luò)堵塞，使網(wǎng)絡(luò)的數(shù)據(jù)分組成功到達(dá)率急劇下降。而本文所提的DDSM和LEMMA都采用TDMA機(jī)制，充分考慮了干擾和沖突避免，數(shù)據(jù)匯聚階段沒(méi)有數(shù)據(jù)碰撞重傳的問(wèn)題，所以網(wǎng)絡(luò)規(guī)模的擴(kuò)大對(duì)數(shù)據(jù)分組成功到達(dá)率影響不大。

圖12 不同τ下的數(shù)據(jù)分組成功到達(dá)率（n=3）

圖13 不同圓環(huán)總數(shù)下數(shù)據(jù)分組成功到達(dá)率

圖14給出了網(wǎng)絡(luò)采用4種數(shù)據(jù)收集協(xié)議在不同的數(shù)據(jù)采集周期(T)下的數(shù)據(jù)分組成功到達(dá)率。從圖 14中可以看出，當(dāng)數(shù)據(jù)采集周期變大時(shí)，即節(jié)點(diǎn)的感應(yīng)數(shù)據(jù)分組產(chǎn)生頻率降低時(shí)，網(wǎng)絡(luò)采用DDSM 和 LEMMA協(xié)議時(shí)的數(shù)據(jù)分組成功到達(dá)率基本保持不變，且維持在90%以上，這是由于這2種協(xié)議采用TDMA機(jī)制；而AIMRP和S-MAC這2種協(xié)議的數(shù)據(jù)分組成功到達(dá)率則相應(yīng)增加，這是由于隨著感應(yīng)數(shù)據(jù)分組產(chǎn)生頻率的降低，節(jié)點(diǎn)間碰撞的概率也相應(yīng)降低。

圖14 不同數(shù)據(jù)采集周期下數(shù)據(jù)分組成功到達(dá)率

圖15給出了網(wǎng)絡(luò)采用4種數(shù)據(jù)收集協(xié)議在不同的節(jié)點(diǎn)分布密度下數(shù)據(jù)分組成功到達(dá)率。從圖15可以看出，當(dāng)節(jié)點(diǎn)分布密度增加時(shí)，即網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量增加，DDSM和LEMMA變化不大，保持在90%以上。DDSM的數(shù)據(jù)分組成功到達(dá)率甚至略有增加，這是因?yàn)楣?jié)點(diǎn)數(shù)量的增加提高了節(jié)點(diǎn)下一跳可以連通的概率（式(18)），而AIMRP和S-MAC這2種協(xié)議的數(shù)據(jù)分組成功到達(dá)率則不斷下降，這是因?yàn)楣?jié)點(diǎn)數(shù)量的增加也增加了網(wǎng)絡(luò)信道碰撞的幾率。

圖15 不同節(jié)點(diǎn)分布密度下數(shù)據(jù)分組成功到達(dá)率

圖16給出了網(wǎng)絡(luò)采用3種數(shù)據(jù)收集協(xié)議時(shí)節(jié)點(diǎn)平均功耗的比值，分別是AIMRP與DDSM的比值，以及S-MAC和DDSM的比值。圖16充分體現(xiàn)了DDSM能量高效的特點(diǎn)，也說(shuō)明了DDSM中采用的 TDMA機(jī)制非常適合無(wú)線傳感器網(wǎng)絡(luò)節(jié)省能量的要求，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)建立了優(yōu)化路由與時(shí)隙調(diào)度表后，在感應(yīng)數(shù)據(jù)向匯聚節(jié)點(diǎn)傳輸?shù)倪^(guò)程中不需要多余的控制信息，也沒(méi)有數(shù)據(jù)碰撞重傳的問(wèn)題；AIMRP協(xié)議中的RTR/CTR/DATA/ACK握手機(jī)制，過(guò)程繁瑣且耗能；S-MAC協(xié)議要求節(jié)點(diǎn)周期性的偵聽(tīng)，并且節(jié)點(diǎn)還需要周期性的廣播自己的調(diào)度信息，這都大量的消耗了節(jié)點(diǎn)的能量。需要注意的是，圖 16中，在網(wǎng)絡(luò)中僅有一個(gè)圓環(huán)時(shí)，與網(wǎng)絡(luò)中具有多個(gè)圓環(huán)的情況相比，DDSM中節(jié)點(diǎn)的平均功耗要遠(yuǎn)低于其他2種數(shù)據(jù)收集協(xié)議，這是因?yàn)榫W(wǎng)絡(luò)中僅有一個(gè)圓環(huán)時(shí)，節(jié)點(diǎn)不再需要轉(zhuǎn)發(fā)來(lái)自外層圓環(huán)中節(jié)點(diǎn)的數(shù)據(jù)，只需要把自身感應(yīng)數(shù)據(jù)發(fā)給匯聚節(jié)點(diǎn)，所以在DDSM中，此時(shí)節(jié)點(diǎn)無(wú)需進(jìn)入偵聽(tīng)狀態(tài)，也就降低了節(jié)點(diǎn)的功耗。可見(jiàn)，空閑偵聽(tīng)的能耗在節(jié)點(diǎn)的總能量消耗中占據(jù)了較大的比例。

圖16 采用不同協(xié)議時(shí)節(jié)點(diǎn)平均功耗的比值

圖17給出了網(wǎng)絡(luò)分別采用DDSM和LEMMA協(xié)議時(shí)，在不同圓環(huán)的總數(shù)下節(jié)點(diǎn)的平均功耗?？梢钥闯?，網(wǎng)絡(luò)采用LEMMA協(xié)議時(shí)，節(jié)點(diǎn)的功耗較高，這是因?yàn)長(zhǎng)EEMA采用的最小跳數(shù)路由并不一定是最小能耗路由，其節(jié)能效果不如DDSM。

圖18反映了網(wǎng)絡(luò)分別采用DDSM和LEMMA協(xié)議時(shí)，在不同圓環(huán)的總數(shù)下網(wǎng)絡(luò)的生命周期比較。其中，網(wǎng)絡(luò)中各節(jié)點(diǎn)的初始能量為1 mJ，網(wǎng)絡(luò)的生命周期值定義為從網(wǎng)絡(luò)開(kāi)始運(yùn)行持續(xù)到網(wǎng)絡(luò)中 1%的節(jié)點(diǎn)耗盡能量為止?？梢钥闯觯W(wǎng)絡(luò)采用DDSM 協(xié)議時(shí)的生命周期較網(wǎng)絡(luò)采用 LEMMA協(xié)議時(shí)長(zhǎng)，這是因?yàn)镈DSM中，節(jié)點(diǎn)在選擇路由時(shí)既考慮了路由的能耗，又限制了節(jié)點(diǎn)作為中繼節(jié)點(diǎn)的次數(shù)，從而延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖17 DDSM和LEMMA下節(jié)點(diǎn)的平均功耗

圖18 DDSM和LEMMA下網(wǎng)絡(luò)的生命周期比較

8 結(jié)束語(yǔ)

本文分析了大規(guī)模的周期匯報(bào)型無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)，并針對(duì)大規(guī)模的周期匯報(bào)型無(wú)線傳感器網(wǎng)絡(luò)提出了一種基于分布式與聯(lián)合優(yōu)化的數(shù)據(jù)匯聚機(jī)制(簡(jiǎn)稱 DDSM)。該機(jī)制采用分布式與跨層設(shè)計(jì)的思想，融合MAC層與網(wǎng)絡(luò)層功能，設(shè)計(jì)基于分布式的跨層數(shù)據(jù)匯聚機(jī)制及其實(shí)現(xiàn)算法，有效提高了網(wǎng)絡(luò)的能量利用效率，降低了網(wǎng)絡(luò)的成本，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

[1] 朱紅松, 孫利民, 徐勇軍等. 基于精細(xì)化梯度的無(wú)線傳感器網(wǎng)絡(luò)匯聚機(jī)制及分析[J]. 軟件學(xué)報(bào),2007,18(5): 1138-1151.ZHU H S, SUN L M, XU Y J,et al. Mechanism and analysis on fine-grain gradient sinking model in wireless sensor networks[J].Journal of Software, 2007, 18(5):1138-1151.

[2] 王辛果, 張信明, 陳國(guó)良. 時(shí)延受限且能量高效的無(wú)線傳感器網(wǎng)絡(luò)跨層路由[J]. 軟件學(xué)報(bào), 2011,22(7):1626-1640.WANG X G, ZHANG X M, CHEN G L. Delay- constrained and energy-efficient cross-layer routing in wireless sensor networks[J]. Journal of Software, 2011, 22 (7):1626-1640.

[3] LUCAS D P, MENDES, JOEL J P C,et al. A survey on cross-layer solutions for wireless sensor networks[J]. Journal of Network and Computer Applications, 2011, 34(2):523-534.

[4] WENDI B. HEINZELMAN, ANANTHA P,et al. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans. Wireless Comm., 2002, 1(4):660-670.

[5] YE W, JOHN H,et al. An energy-efficient MAC protocol for wireless sensor networks[A]. Proc IEEE INFOCOM[C]. 2002.1567-1576.

[6] 李哲濤,朱更明,王志強(qiáng)等.低占空比、低碰撞的異步無(wú)線傳感器網(wǎng)絡(luò)MAC協(xié)議[J].通信學(xué)報(bào), 2013,34(10):9-16.LI Z T, ZHU G M, WANG Z Q,et al. Low duty cycle and low collision asynchronous MAC protocol for wireless sensor network[J].Journal on Communications, 2013,34(10):9-16.

[7] GEOFFREY G. MESSIER, JENNIFER A,et al, DAVIES. A sensor network cross-layer power control algorithm that incorporates multiple-access interference[J]. IEEE Transactions on Wireless Communications, 2008, 7(8):2877-2883.

[8] 李方敏, 劉新華, 徐文君等. 無(wú)線傳感器網(wǎng)絡(luò)的鏈路穩(wěn)定成簇與功率控制算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(6): 968-978.LI F M, LIU X H, XU W J,et al. Link-stable clustering and power control for wireless sensor networks[J]. Chinese Journal of Computers,2008, 31(6):968-978.

[9] KULKARNI S, IYER A, ROSENBERG C. An address-light, integrated MAC and routing protocol for wireless sensor networks[J].IEEE/ACM Transactions on Networking, 2006, 14(4):793-806.

[10] SHI L Q, ABRAHAM O, FAPOJUW O. TDMA scheduling with optimized energy efficiency and minimum delay in clustered wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2010,9(7):927-940.

[11] 鄭國(guó)強(qiáng), 李建東, 周志李. 多跳無(wú)線傳感器網(wǎng)絡(luò)的高能效數(shù)據(jù)收集協(xié)議[J]. 軟件學(xué)報(bào), 2010, 21(9): 2320-2337.ZHENG G Q, LI J D, ZHOU Z L. Energy-efficient data gathering protocol for multihop wireless sensor networks[J]. Journal of Software,2010, 21(9): 2320-2337.

[12] MACEDO M, GRILO A, NUNES M. Distributed latency-energy minimization and interference avoidance in TDMA wireless sensor networks[J]. Computer Networks, 2009, 53(5):569-582.

[13] 曾志文, 陳志剛, 劉安豐. 無(wú)線傳感器網(wǎng)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J], 計(jì)算機(jī)學(xué)報(bào), 2010, 33(1):12-22.ZENG Z W, CHEN Z G, LIU A F. Energy-hole avoidance for WSN based on adjust transmission power[J]. Chinese Journal of Computers,2010, 33(1):12-22.

[14] RAPPAPORT T. Wireless Communications: Principles and Practice[M]. Prentice Hall, New Jersey, 1996.

[15] 張克旺,張德運(yùn),杜君.面向多跳無(wú)線網(wǎng)絡(luò)的無(wú)沖突MAC協(xié)議[J]. 軟件學(xué)報(bào), 2009,20(7):1895-1908.ZHANG K W,ZHANG D Y,DU J. Collision free MAC protocol for multi- hop wireless networks[J]. Journal of Software, 2009,20(7):1895-1908.

[16] XU K X, GERLA M, SANG B. How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[A]. Proc of the IEEE Global Telecommunications Conf[C]. 2002.72-76.

[17] 吳小兵,陳貴海.無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)非均勻分布的能量空洞問(wèn)題[J].計(jì)算機(jī)學(xué)報(bào),2008,31(2):253-261.WU X B, CHEN G H. The energy hole problem of nonuniform node distribution in wireless sensor networks [J]. Chinese Journal of Computers,2008,31(2):253-261.

[18] WANG Y, WANG X D, XIE B,et al. Intrusion detection in homogeneous and heterogeneous wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2008,7(6):698-711.