林鐘楷，程良倫

（廣東工業(yè)大學(xué)自動(dòng)化學(xué)院控制網(wǎng)絡(luò)與系統(tǒng)研究所，廣東廣州 510006）

0 引言

目前，大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)（WSNs）的路由協(xié)議大多采用了樹狀拓?fù)浣Y(jié)構(gòu)［1］，通過(guò)分簇和Sink節(jié)點(diǎn)實(shí)現(xiàn)分層管理，以減少網(wǎng)絡(luò)控制的復(fù)雜程度。針對(duì)這種結(jié)構(gòu)，文獻(xiàn)［2］中Lu G等人提出一種基于路徑規(guī)劃原則的DMAC協(xié)議，根據(jù)數(shù)據(jù)的傳輸路徑來(lái)規(guī)劃信道，引入交錯(cuò)的監(jiān)聽睡眠調(diào)度機(jī)制，保證數(shù)據(jù)在多跳路徑上的連續(xù)傳輸。文獻(xiàn)［3］中的Barroso A等人提出以簇為規(guī)劃核心的混合型協(xié)議μ-MAC，該協(xié)議以Sink節(jié)點(diǎn)為核心，向上與其它Sink節(jié)點(diǎn)對(duì)信道實(shí)行競(jìng)爭(zhēng)，向下對(duì)下層節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)和分配，實(shí)現(xiàn)節(jié)點(diǎn)的有序接入。而文獻(xiàn)［4］中，古連華等人對(duì)文獻(xiàn)［3］做了改進(jìn)，通過(guò)加入下層節(jié)點(diǎn)到Sink節(jié)點(diǎn)的數(shù)據(jù)通信預(yù)約機(jī)制，進(jìn)一步提高了網(wǎng)絡(luò)的自適應(yīng)性。文獻(xiàn)［5］則進(jìn)一步對(duì)網(wǎng)絡(luò)進(jìn)行劃分，引入了虛擬群的結(jié)構(gòu)，提出了基于虛擬群的信道接入和休眠管理體制，強(qiáng)化了網(wǎng)絡(luò)的管理，避免了沖突和時(shí)延。

上述協(xié)議在一定程度上能夠解決大規(guī)模節(jié)點(diǎn)分布的網(wǎng)絡(luò)中的能量和效率問(wèn)題，但僅僅參考節(jié)點(diǎn)的自身資源，沒有考慮到隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大所帶來(lái)的簇的規(guī)模擴(kuò)大化和結(jié)構(gòu)復(fù)雜化。當(dāng)網(wǎng)絡(luò)規(guī)模過(guò)大時(shí)容易帶來(lái)簇與簇之間的相互牽擾，以及簇內(nèi)節(jié)點(diǎn)過(guò)多帶來(lái)的劇烈競(jìng)爭(zhēng)問(wèn)題。本文提出一種基于大規(guī)模網(wǎng)絡(luò)分解和協(xié)調(diào)的自適應(yīng)MAC協(xié)議（an adaptive MAC protocol based on decomposition and coordination of large-scale networks，ABDC-MAC），其主要思想是:按照網(wǎng)絡(luò)層次和時(shí)間關(guān)聯(lián)性，使用文獻(xiàn)［6］提出的分解方法對(duì)樹狀拓?fù)浣Y(jié)構(gòu)進(jìn)行串行和并行劃分，同時(shí)引入網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)資源、通信時(shí)間等因子，采用文獻(xiàn)［7］中提出的RBRS方法對(duì)節(jié)點(diǎn)參與網(wǎng)絡(luò)競(jìng)爭(zhēng)的概率進(jìn)行調(diào)整。該協(xié)議實(shí)現(xiàn)了網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化，大大減少了復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)帶來(lái)的能量和通信問(wèn)題。

1 協(xié)議的提出

1.1 網(wǎng)絡(luò)結(jié)構(gòu)

假定存在如圖1所示樹狀結(jié)構(gòu)，同質(zhì)節(jié)點(diǎn)隨機(jī)分布在正方形區(qū)域中，基站（BS）的能量不受限制，節(jié)點(diǎn)周期性地遙感所有傳感器的數(shù)據(jù)，并通過(guò)多對(duì)一的匯聚模式逐級(jí)由子節(jié)點(diǎn)向父節(jié)點(diǎn)傳輸，并最終匯集到Sink節(jié)點(diǎn)，再由Sink節(jié)點(diǎn)傳遞到基站。在這種樹狀結(jié)構(gòu)中，只有父子關(guān)系的相鄰節(jié)點(diǎn)存在業(yè)務(wù)轉(zhuǎn)發(fā)，但臨近節(jié)點(diǎn)的業(yè)務(wù)時(shí)間相關(guān)性較強(qiáng)。這種結(jié)構(gòu)的父子節(jié)點(diǎn)數(shù)據(jù)關(guān)系與傳統(tǒng)分群協(xié)議中成員與群首的業(yè)務(wù)模式類似。本文在樹狀結(jié)構(gòu)與分群協(xié)議［5］的基礎(chǔ)上，對(duì)網(wǎng)絡(luò)進(jìn)行進(jìn)一步的細(xì)分，通過(guò)降低簇的規(guī)模實(shí)現(xiàn)網(wǎng)絡(luò)的靈活性。

圖1 樹狀拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)Fig 1 Architecture Tree topology network

1.2 ABDC-MAC協(xié)議對(duì)網(wǎng)絡(luò)的分解

本文提出的網(wǎng)絡(luò)分解方法分為串行分解和并行分解［6］2種模式，其分解的最終目標(biāo)是把網(wǎng)絡(luò)分解為包含10～20個(gè)節(jié)點(diǎn)的子項(xiàng)目組，每個(gè)項(xiàng)目組有一個(gè)現(xiàn)實(shí)（通過(guò)串行分解）或者虛擬（通過(guò)并行分解）的父節(jié)點(diǎn)。首先，對(duì)網(wǎng)絡(luò)使用串行分解，得到第一層的子節(jié)點(diǎn)群，然后對(duì)數(shù)量大于20的子節(jié)點(diǎn)群使用串行分解，得到第二層的子節(jié)點(diǎn)群，繼續(xù)對(duì)未達(dá)到分解目標(biāo)的節(jié)點(diǎn)群繼續(xù)進(jìn)行分解，直到達(dá)成分解目標(biāo)為止。同時(shí)在每一層引入并行分解機(jī)制，對(duì)每一層的子節(jié)點(diǎn)數(shù)目進(jìn)行限制。

1）串行分解

串行分解主要通過(guò)查找節(jié)點(diǎn)的傳播路徑來(lái)實(shí)現(xiàn)，按照網(wǎng)絡(luò)的樹狀架構(gòu)，各個(gè)節(jié)點(diǎn)的信息總是通過(guò)多對(duì)一的匯聚模式逐步向Sink節(jié)點(diǎn)和基站匯合，與匯聚節(jié)點(diǎn)相關(guān)的節(jié)點(diǎn)構(gòu)成了一個(gè)子節(jié)點(diǎn)群，而匯聚節(jié)點(diǎn)本身則作為該群的父節(jié)點(diǎn)存在。串行分解就是k－1層匯聚節(jié)點(diǎn)對(duì)與其有數(shù)據(jù)關(guān)聯(lián)關(guān)系的k層節(jié)點(diǎn)的劃分，通過(guò)對(duì)k層節(jié)點(diǎn)上傳數(shù)據(jù)的關(guān)聯(lián)關(guān)系進(jìn)行鑒別，區(qū)分出匯聚節(jié)點(diǎn)及其關(guān)聯(lián)節(jié)點(diǎn)，并重新定義匯聚節(jié)點(diǎn)為k層節(jié)點(diǎn)，與匯聚節(jié)點(diǎn)關(guān)聯(lián)的節(jié)點(diǎn)為其子節(jié)點(diǎn)k+1層。同時(shí)，對(duì)除了匯聚節(jié)點(diǎn)及其關(guān)聯(lián)節(jié)點(diǎn)之外的獨(dú)立節(jié)點(diǎn)暫時(shí)將其分在k層。串行分解后，會(huì)形成以k層匯聚節(jié)點(diǎn)為父節(jié)點(diǎn)的群和零散的獨(dú)立節(jié)點(diǎn)。

2）并行分解

串行分解完成后，如果k層同時(shí)存在匯聚節(jié)點(diǎn)和獨(dú)立節(jié)點(diǎn)，或者獨(dú)立節(jié)點(diǎn)的個(gè)數(shù)超過(guò)分解目標(biāo)，則對(duì)獨(dú)立節(jié)點(diǎn)進(jìn)行并行分解，其原則如下:

a.使得該集合中的所有節(jié)點(diǎn)與其它節(jié)點(diǎn)的活動(dòng)沒有時(shí)序關(guān)系;

b.若完成a步驟后，該集合中的節(jié)點(diǎn)數(shù)超過(guò)分解目標(biāo)的，則對(duì)該集合進(jìn)行切割，通過(guò)設(shè)置時(shí)間標(biāo)志，將集合中的節(jié)點(diǎn)按照時(shí)間關(guān)系分割為2個(gè)集合;

c.若完成b步驟后，集合中的節(jié)點(diǎn)數(shù)仍超過(guò)分解目標(biāo)，則繼續(xù)執(zhí)行b步驟;

d.對(duì)于每個(gè)集合，隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為虛擬父節(jié)點(diǎn)，位于k層，而其余節(jié)點(diǎn)為子節(jié)點(diǎn)，位于k+1層。

同時(shí)，若匯聚節(jié)點(diǎn)與虛擬匯聚節(jié)點(diǎn)的數(shù)量超過(guò)分割目標(biāo)，同樣進(jìn)行并行分解，其分解原則與獨(dú)立節(jié)點(diǎn)的分解原則相同，但最后的虛擬父節(jié)點(diǎn)由k－1層的相關(guān)匯聚節(jié)點(diǎn)擔(dān)任。

通過(guò)上述的串行和并行分解，網(wǎng)絡(luò)的結(jié)構(gòu)如圖2所示。由于進(jìn)行了基于路徑和時(shí)間的分解，各個(gè)最小群組間的時(shí)序關(guān)系達(dá)到了最小關(guān)聯(lián)，最大可能性地減小了群間通信的串?dāng)_。

圖2 ABDC-MAC協(xié)議拓?fù)浣Y(jié)構(gòu)Fig 2 ABDC-MAC topology

1.3 ABDC-MAC協(xié)議的運(yùn)行

本文提出的ABDC-MAC協(xié)議的運(yùn)行分為兩部分:建立階段和運(yùn)行階段。在建立階段，主要是對(duì)網(wǎng)絡(luò)的分割、同步和初始化。而在運(yùn)行階段，主要是節(jié)點(diǎn)自身網(wǎng)絡(luò)參數(shù)的主動(dòng)調(diào)整與上傳，使得整個(gè)網(wǎng)絡(luò)參數(shù)得到調(diào)整，適應(yīng)網(wǎng)絡(luò)流量的動(dòng)態(tài)變化。

1.3.1 建立階段

建立階段主要是分為2步:對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行串行和并行分解，并建立節(jié)點(diǎn)的上下層節(jié)點(diǎn)信息表和處理節(jié)點(diǎn)同步問(wèn)題，同時(shí)采集節(jié)點(diǎn)的初始信息。具體步驟如下:

1）網(wǎng)絡(luò)分割

在網(wǎng)絡(luò)的分割階段:1）由Sink節(jié)點(diǎn)做一個(gè)長(zhǎng)度為一個(gè)調(diào)度周期的開始信號(hào)廣播，Sink節(jié)點(diǎn)下屬的子節(jié)點(diǎn)收到開始信號(hào)后，將持續(xù)監(jiān)聽網(wǎng)絡(luò);2）每一層的匯聚節(jié)點(diǎn)使用嵌套點(diǎn)名法對(duì)其直屬的子節(jié)點(diǎn)進(jìn)行點(diǎn)名，得到回應(yīng)后向其傳遞下一層的隸屬節(jié)點(diǎn)信息和簡(jiǎn)單同步信息。當(dāng)子節(jié)點(diǎn)的點(diǎn)名完成后，向上一級(jí)匯聚節(jié)點(diǎn)報(bào)告。嵌套點(diǎn)名法如圖3所示;3）對(duì)于獨(dú)立節(jié)點(diǎn)的虛擬父節(jié)點(diǎn)采取同樣的方法，對(duì)于匯聚節(jié)點(diǎn)的虛擬父節(jié)點(diǎn)，則對(duì)其每一個(gè)子節(jié)點(diǎn)進(jìn)行點(diǎn)名。

同時(shí)，節(jié)點(diǎn)上會(huì)建立上游信息表（表1）和下游信息表（表2），對(duì)上下游的節(jié)點(diǎn)進(jìn)行登記和管理，主要用于休眠時(shí)間同步和網(wǎng)絡(luò)參數(shù)計(jì)算。其中，R，T和NS為節(jié)點(diǎn)的資源負(fù)載參數(shù)、時(shí)延參數(shù)以及網(wǎng)絡(luò)復(fù)雜度參數(shù)。

表1 上游信息表Tab 1 Present node’s info

表2 下游信息表Tab 2 Child node’s info

圖3 使用嵌套點(diǎn)名法對(duì)節(jié)點(diǎn)進(jìn)行分割Fig 3 Decomposition the network by roll-call method

2） 休眠時(shí)間同步和節(jié)點(diǎn)信息初始化

休眠時(shí)間的同步和節(jié)點(diǎn)信息初始化由該網(wǎng)絡(luò)的父節(jié)點(diǎn)發(fā)起，父節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)承載業(yè)務(wù)和時(shí)延要求設(shè)定休眠占空比，并選擇休眠開始時(shí)間進(jìn)行廣播，其他節(jié)點(diǎn)接收后，根據(jù)上游信息表確定時(shí)候?yàn)楦腹?jié)點(diǎn)，若是，則在調(diào)度信息中加入，否則，丟棄。調(diào)度信息記錄完成后，節(jié)點(diǎn)上傳Rs，Ts，NSs和時(shí)鐘參數(shù)，父節(jié)點(diǎn)接收后，反饋時(shí)鐘漂移校正參數(shù)，并完成本次同步過(guò)程。

1.3.2 運(yùn)行階段

ABDC-MAC協(xié)議的運(yùn)行模式如圖4所示:

1）協(xié)議總體上采用競(jìng)爭(zhēng)型架構(gòu)，在每一層由父節(jié)點(diǎn)（包括虛擬父節(jié)點(diǎn)）競(jìng)爭(zhēng)一定時(shí)長(zhǎng)的信道使用權(quán)，父節(jié)點(diǎn)競(jìng)爭(zhēng)到信道使用權(quán)后，將使用權(quán)劃分為多個(gè)時(shí)長(zhǎng)，由其子節(jié)點(diǎn)競(jìng)爭(zhēng)。

2）父節(jié)點(diǎn)對(duì)信道的競(jìng)爭(zhēng)原則與文獻(xiàn)［8］的原則類似，但引入一個(gè)參數(shù)P（s）。該參數(shù)代表節(jié)點(diǎn)在信道競(jìng)爭(zhēng)階段選擇接入信道的概率。該參數(shù)與父節(jié)點(diǎn)及其下屬子節(jié)點(diǎn)的資源負(fù)載R，子節(jié)點(diǎn)與父節(jié)點(diǎn)的通信時(shí)長(zhǎng)T和該節(jié)點(diǎn)群的網(wǎng)絡(luò)復(fù)雜程度NS，以及競(jìng)爭(zhēng)期時(shí)隙選擇有關(guān)。同時(shí)需要指出的是，節(jié)點(diǎn)在上傳數(shù)據(jù)的時(shí)候，還需將自己現(xiàn)在的Rs，Ts和NSs參數(shù)上傳，作為上級(jí)節(jié)點(diǎn)的計(jì)算參考值。

3）子節(jié)點(diǎn)對(duì)信道的偵聽采用跟隨監(jiān)聽方式，即從頂層節(jié)點(diǎn)開始跟蹤，若在一個(gè)競(jìng)爭(zhēng)周期內(nèi)檢測(cè)到得到信道使用權(quán)的節(jié)點(diǎn)不是自己的上級(jí)節(jié)點(diǎn)的時(shí)候，會(huì)轉(zhuǎn)入休眠節(jié)點(diǎn)直到下一個(gè)周期的到來(lái);若為自己的上級(jí)節(jié)點(diǎn)，則會(huì)逐級(jí)跟蹤，直至到達(dá)自己的額競(jìng)爭(zhēng)周期為止。

4）對(duì)于底層節(jié)點(diǎn)，由于其數(shù)目較少（小于預(yù)訂分解目標(biāo)20），故采取輪詢的方法，一次性采集20個(gè)節(jié)點(diǎn)的數(shù)據(jù)并在上層父節(jié)點(diǎn)整合上傳。

5）若遇到路由協(xié)議更換Sink節(jié)點(diǎn)的情況，則只對(duì)出現(xiàn)變動(dòng)的分組進(jìn)行重新分解，以減少由組織網(wǎng)絡(luò)帶來(lái)的時(shí)間和能量損耗。

圖4 ABDC-MAC協(xié)議的運(yùn)行Fig 4 Operation of ABDC-MAC protocal

2 仿真與實(shí)驗(yàn)分析

本文提出的ABDC-MAC協(xié)議在NS-2平臺(tái)進(jìn)行仿真，為了對(duì)比評(píng)價(jià)，同時(shí)實(shí)現(xiàn)了ABDC-MAC和S-MAC協(xié)議。測(cè)試的性能指標(biāo)有:ABDC-MAC的組網(wǎng)效率，ABDC-MAC協(xié)議與S-MAC協(xié)議的節(jié)能效率和網(wǎng)絡(luò)延時(shí)對(duì)比。網(wǎng)絡(luò)的主要設(shè)定參數(shù)如表3所示。

表3 仿真參數(shù)Tab 3 Network simulation parameter

表4列出了ABDC-MAC協(xié)議的組網(wǎng)效率，可以看出:當(dāng)網(wǎng)絡(luò)初始化或者其構(gòu)造發(fā)生較大的變動(dòng)的時(shí)候，ABDCMAC協(xié)議需要較長(zhǎng)的一段時(shí)間進(jìn)行組網(wǎng);而當(dāng)由于路由更換Sink節(jié)點(diǎn)等原因發(fā)生小范圍的變化時(shí)，ABDC-MAC協(xié)議可以較快地調(diào)整好網(wǎng)絡(luò)。

表4 組網(wǎng)效率Tab 4 Networking efficiency

由圖5可以看出:在運(yùn)行中，由于節(jié)點(diǎn)只需偵聽與自己有關(guān)的上層節(jié)點(diǎn)是否得到網(wǎng)絡(luò)，而不必每個(gè)時(shí)段都進(jìn)行偵聽，ABDC-MAC協(xié)議運(yùn)行階段的能耗遠(yuǎn)遠(yuǎn)低于一般競(jìng)爭(zhēng)型協(xié)議。不僅很好地彌補(bǔ)了組網(wǎng)階段的能耗，在總體能耗上也有很大降低。

圖5 節(jié)點(diǎn)平均能耗Fig 5 Average power consumption of each node

由圖6分別列出了ABDC-MAC協(xié)議對(duì)比S-MAC協(xié)議的網(wǎng)絡(luò)延時(shí)?？梢钥闯?雖然增加網(wǎng)絡(luò)復(fù)雜度帶來(lái)了一定的網(wǎng)絡(luò)延時(shí)，但由于大規(guī)模網(wǎng)絡(luò)下組網(wǎng)更加合理，帶來(lái)的碰撞和重傳次數(shù)的減少，節(jié)點(diǎn)的延時(shí)大致與S-MAC協(xié)議相近，在數(shù)據(jù)量大的情況下甚至優(yōu)于S-MAC協(xié)議。

圖6 節(jié)點(diǎn)時(shí)延性能實(shí)驗(yàn)Fig 6 Time delay property experiment of nodes

3 結(jié)論

本文提出一種基于大規(guī)模網(wǎng)絡(luò)分解和協(xié)調(diào)的自適應(yīng)MAC協(xié)議，該協(xié)議通過(guò)對(duì)網(wǎng)絡(luò)的二次重構(gòu)和節(jié)點(diǎn)的優(yōu)先級(jí)計(jì)算實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)的有序化。仿真結(jié)果表明:在大規(guī)模組網(wǎng)的情況下，該協(xié)議總體能耗低、傳達(dá)率高，且具有一定的自適應(yīng)性，同時(shí)網(wǎng)絡(luò)時(shí)延并沒有因?yàn)榉謱佣黾?。該協(xié)議對(duì)大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)有良好的適用性。

［1］Krishnamachari B，Estrin D，wicker S.The impact of data aggregation in wireless sensor networks［C］//The 22nd International Conference on Distributed Computing Systems Workshops，Vienna，Austria，2002:575 －578.

［2］Lu G，Krishnamachari B，Raghavendra C S.An adaptive energyefficient and low-latency MAC for data gathering in wireless sensor networks［J］.IEEE IPDPS，2004，224:26 －30.

［3］Barroso A，Roedig U，Sreenan C.μ-MAC:An energy-efficient medium access control for wireless sensor networks［C］//Proc of European Workshop on Wireless Sensor Networks，2005:

［4］古連華，程良倫.A μ-MAC:一種自適應(yīng)的無(wú)線傳感器網(wǎng)絡(luò)MAC 協(xié)議［J］.自動(dòng)化學(xué)報(bào)，2010，1:54－59.

［5］Li J，Lazarou G.A bit-map-assisted energy efficient MAC scheme for wireless sensor networks［C］//The 3rd Int’l Symp on Information Processing in Sensor Networks，IPSN 04，New York，2004:55－60.

［6］程 序，吳 澄.大規(guī)模項(xiàng)目調(diào)度問(wèn)題的分解和協(xié)調(diào)優(yōu)化方法［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，2009，49:40 －43.

［7］Herrolen W，Reyck B D，Demeulemeester E.Resource constrained project scheduling:A survey of recent develop-ments［J］.Computers＆ Operations Research，1998，25（4）:279 －302.

［8］Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks［C］//Proc 21st Int’l Annual Joint Conf on Computer and Communications Societies，IEEE，New York，2002.