一種基于Quorum系統(tǒng)的異步傳感網(wǎng)局部時(shí)間分配算法

楊 璐

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 211189)

(東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京 211189)

一種基于Quorum系統(tǒng)的異步傳感網(wǎng)局部時(shí)間分配算法

楊 璐

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 211189)

(東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京 211189)

為了在無(wú)線傳感器網(wǎng)絡(luò)中增強(qiáng)節(jié)點(diǎn)通信時(shí)間分配的公平性，設(shè)計(jì)了一種局部的按需異步時(shí)間分配算法(SATA).SATA算法的設(shè)計(jì)基于Quorum系統(tǒng)(Quorum system，QS).首先構(gòu)造出一個(gè)QS，然后節(jié)點(diǎn)根據(jù)自身的通信量在QS中選擇合適數(shù)量的活動(dòng)時(shí)隙，并通知其鄰居節(jié)點(diǎn)，這樣可以消除信道競(jìng)爭(zhēng)，保證每對(duì)相鄰節(jié)點(diǎn)能夠擁有適當(dāng)?shù)墓不顒?dòng)時(shí)隙來(lái)完成通信的需求.由于所構(gòu)造的QS滿足旋轉(zhuǎn)封閉性，所以即使在節(jié)點(diǎn)時(shí)鐘不準(zhǔn)確并且不使用時(shí)間同步協(xié)議的情況下，SATA也能夠保證網(wǎng)絡(luò)的連通性.理論分析和實(shí)驗(yàn)驗(yàn)證表明，SATA能夠提高信道利用率、節(jié)省能耗以及提高網(wǎng)絡(luò)吞吐量.

異步時(shí)間分配;占空比;Quorum系統(tǒng);無(wú)線傳感網(wǎng)

在無(wú)線傳感網(wǎng)絡(luò)中，協(xié)調(diào)傳感器節(jié)點(diǎn)(簡(jiǎn)稱節(jié)點(diǎn))之間通信時(shí)間和信道的重要機(jī)制是MAC協(xié)議［1］.該協(xié)議通過協(xié)調(diào)節(jié)點(diǎn)間共享媒介，來(lái)建立節(jié)點(diǎn)間的通信和分配節(jié)點(diǎn)間的通信時(shí)間［2］.MAC協(xié)議可分為基于TDMA和CSMA兩類.基于TDMA的MAC協(xié)議其優(yōu)點(diǎn)是為每個(gè)節(jié)點(diǎn)事先安排好工作時(shí)隙，這樣可以減少與鄰居的碰撞，并達(dá)到高效的信道使用率和降低能耗的效果.這類協(xié)議工作的前提是需要節(jié)點(diǎn)間的時(shí)間同步，如FTSP［3］，但是時(shí)間同步協(xié)議能耗大、耗時(shí)長(zhǎng)，在網(wǎng)絡(luò)規(guī)模大的情況下，收斂性無(wú)法得到保證［3］.雖然基于CSMA協(xié)議不需要嚴(yán)格地與時(shí)鐘同步，但是它不能實(shí)現(xiàn)與TDMA同樣的信道高效使用，在節(jié)點(diǎn)競(jìng)爭(zhēng)媒介的過程中，造成節(jié)點(diǎn)額外的時(shí)間和能量消耗.因此低功率偵聽技術(shù)(low power listening，LPL)被引入了基于CSMA 的 MAC 協(xié)議中，如 B-MAC［4］，S-MAC［3］和 TMAC［5］.這些MAC協(xié)議本質(zhì)上采用LPL或改善的LPL技術(shù)，以緩解時(shí)鐘不同步問題.盡管基于CSMA的協(xié)議在時(shí)鐘不同步情況下較有優(yōu)勢(shì)，但它依然無(wú)法避免信道競(jìng)爭(zhēng)，無(wú)法獲得信道分配公平［6］.因此，在不需要節(jié)點(diǎn)時(shí)鐘同步協(xié)議的情況下，增加在媒介訪問時(shí)間資源分配方面的公平性，同時(shí)還要盡可能地降低能耗.

為了解決上述問題，本文基于Quorum系統(tǒng)［7］(Quorum system，QS)設(shè)計(jì)了一種局部的按需異步時(shí)間分配方法(SATA).SATA能使每個(gè)節(jié)點(diǎn)根據(jù)自身的通信量選擇適當(dāng)數(shù)量的活動(dòng)時(shí)隙，這些活動(dòng)時(shí)隙組成一個(gè)集合，記為 .在QS中，一個(gè)周期T是由多個(gè)時(shí)隙子集quorum組成的集合，?T.因此，當(dāng)調(diào)整活動(dòng)時(shí)隙數(shù)量，相應(yīng)地也改變了占空比.SATA方法中，每個(gè)節(jié)點(diǎn)將自己的活動(dòng)時(shí)隙 通知其鄰居節(jié)點(diǎn)，鄰居可以選擇其他時(shí)隙子集，由此它們之間的信道競(jìng)爭(zhēng)便可消除.在節(jié)點(diǎn)時(shí)鐘不準(zhǔn)確的情況下，SATA無(wú)需采用時(shí)間同步協(xié)議，也能保證網(wǎng)絡(luò)的連通性，使每個(gè)節(jié)點(diǎn)按照數(shù)據(jù)傳輸量需求自適應(yīng)地調(diào)節(jié)其占空比.

1 網(wǎng)絡(luò)建模和概念

設(shè)V(或E)是所有節(jié)點(diǎn)(或邊)的集合.網(wǎng)絡(luò)所包含的節(jié)點(diǎn)數(shù)記為本文采用RTS/CTS干擾模型(模型I)進(jìn)行相關(guān)理論分析.一個(gè)QS，記為Ω(Ω?2T)，由多個(gè)quorum組成.quorum表示為Q，是T的一個(gè)子集 ，周期T={τ1，τ2，…，τm}由m個(gè)等長(zhǎng)的時(shí)隙構(gòu)成.不同 quorum用Q1，Q2，…，表示.如圖1(a)所示，第2和第6個(gè)quorum為Q2={τ2，τ8，τ14，τ15，τ16，τ17，τ18}，Q6={τ6，τ12，τ17，τ21，τ24，τ26，τ28}.另外，本文將Q的旋轉(zhuǎn)定義為，其中i是一個(gè)非負(fù)整數(shù).在現(xiàn)有的QS中，有部分滿足旋轉(zhuǎn)封閉性，也就是?i∈{1，2，…，m－ 1}:Q1∩R(Q2，i)≠?，Q1，Q2∈Ω.

引理1 網(wǎng)格QS、環(huán)QS和循環(huán)QS滿足旋轉(zhuǎn)封閉性［8］.

引理1說(shuō)明只有某些QS具有旋轉(zhuǎn)封閉性.在節(jié)點(diǎn)需要休眠的情況下，旋轉(zhuǎn)封閉性對(duì)于確保節(jié)點(diǎn)間能夠通信(也即確保節(jié)點(diǎn)間物理連通性)非常重要.特別是節(jié)點(diǎn)時(shí)鐘不同步時(shí)，該性質(zhì)對(duì)于保證節(jié)點(diǎn)間能夠相互通信不可或缺.

圖1 網(wǎng)格QS

易知2個(gè)相鄰節(jié)點(diǎn)u和v，若能彼此通信，它們之間必須有至少一個(gè)共同的活動(dòng)時(shí)隙.而傳感網(wǎng)中節(jié)點(diǎn)時(shí)鐘通常是不準(zhǔn)確的，即一個(gè)節(jié)點(diǎn)u的時(shí)鐘相對(duì)真實(shí)時(shí)間有一個(gè)偏差，記為tuδ≥0.相應(yīng)地，節(jié)點(diǎn)u的所有活動(dòng)時(shí)隙u也有偏差，即'u=u+tuδ.如果一對(duì)相鄰節(jié)點(diǎn)在異步時(shí)鐘下可以完成彼此間的通信，那么應(yīng)滿足以下方程:

式中，θu是以節(jié)點(diǎn)u為中心，在u通信范圍內(nèi)所有節(jié)點(diǎn)的集合.當(dāng)2個(gè)節(jié)點(diǎn)分別屬于對(duì)方的通信集合時(shí)，稱這對(duì)節(jié)點(diǎn)是相鄰的.式(1)意味著，如果2個(gè)相鄰節(jié)點(diǎn)的活動(dòng)時(shí)隙集設(shè)計(jì)得合理，則一對(duì)相鄰節(jié)點(diǎn)的時(shí)鐘即使是異步的，也能有共同的活動(dòng)時(shí)隙進(jìn)行通信.本文定義參數(shù)D表示在單位時(shí)間內(nèi)所需傳輸或者接受的數(shù)據(jù)量，即通信量.而式(1)表示一對(duì)相鄰節(jié)點(diǎn)不僅要有共同的活動(dòng)時(shí)間，也要有足夠的時(shí)間來(lái)完成其通信量.將式(1)中的調(diào)節(jié)及其SATA方法中的節(jié)能目標(biāo)表述為時(shí)間資源分配條件(條件C)，即每對(duì)鄰居節(jié)點(diǎn)有適量的共同活動(dòng)時(shí)隙，能滿足它們之間的通信需求，同時(shí)又能降低占空比以節(jié)省能耗.

為了滿足條件C，每一個(gè)節(jié)點(diǎn)u局部地選擇一個(gè)活動(dòng)時(shí)隙子集'u?T，從而保證θu中的每一對(duì)節(jié)點(diǎn)滿足式(1).本文設(shè)計(jì)了SATA算法，調(diào)節(jié)每個(gè)節(jié)點(diǎn)的占空比，使得時(shí)間資源能夠在節(jié)點(diǎn)間得到合理分配.SATA算法采用引理1所述的具有旋轉(zhuǎn)封閉性的QS，使得時(shí)鐘即便有漂移，也能保證相鄰節(jié)點(diǎn)在盡量低的占空比下，有一定數(shù)量的公共活動(dòng)時(shí)隙，即使得式(1)得到滿足，條件C得以實(shí)現(xiàn).

2 SATA算法設(shè)計(jì)

SATA的設(shè)計(jì)包括2個(gè)步驟:① 設(shè)計(jì)出一個(gè)QS，記為Ω;② 每個(gè)節(jié)點(diǎn)根據(jù)其一跳鄰居信息，局部地選擇其活動(dòng)時(shí)隙集合，即該節(jié)點(diǎn)的quorum.

1)基于周期T先構(gòu)建一個(gè)網(wǎng)格QS:Ω，網(wǎng)格大小為是QS的行列數(shù)，如圖1所示.將T中的時(shí)隙分別分配到網(wǎng)格Ω中，以先列后排的方式從左到右分配到QS的各個(gè)格子中.在每一個(gè)周期中，節(jié)點(diǎn)u根據(jù)需求Du確定其活動(dòng)時(shí)隙集u.u的勢(shì)記為Ku，Ku=mDμ/ρ，其中ρ為數(shù)據(jù)傳輸速率.按如下方式設(shè)計(jì)u的quorumQu:Qu是由第i到行組成的，其中i為行序號(hào)，如圖1(a)中所示，并且i∈Z+以及i

2)Quorum選擇方法(算法1).該方法使得每個(gè)節(jié)點(diǎn)能夠根據(jù)一跳鄰居信息決定自身選擇的quorum及其數(shù)量.在選擇的過程中，一個(gè)quorum難免會(huì)被多個(gè)節(jié)點(diǎn)選擇，這時(shí)候便意味著發(fā)生“quorum選擇沖突”.如圖1(b)所示，如果Qu早于Qv被選擇，則Qu被Qv占據(jù).算法1中的K是經(jīng)驗(yàn)參數(shù)，其取值是預(yù)先給定的整數(shù)值，一般小于QS所含quorum的數(shù)量.

算法1 Quorum選擇方法(SATA)

圖2 quorum選擇示例

下面通過一個(gè)例子來(lái)說(shuō)明算法1的原理.如圖2所示，假設(shè)u，v和w這3個(gè)節(jié)點(diǎn)中，v和w是u的鄰居，v和u之間、w和u之間需要進(jìn)行通信.不失一般性，u先開始選擇其quorum;其所選的quorum為圖 2(a)中的第 5 個(gè)，也即Q5={τ5，τ11，τ16，τ20，τ23，τ26，τ27}.而后，v選擇其 quorum，假設(shè)v和u之間需要交換的數(shù)據(jù)是w和u之間需要交換數(shù)據(jù)的2倍，那么根據(jù)v所需要傳輸?shù)臄?shù)據(jù)量，v選擇2個(gè)quorum，其選的quorum為圖2(a)中的第2和第3個(gè)，也即Q2={τ2，τ8，τ14，τ15，τ16，τ17，τ18}和Q3={τ3，τ9，τ14，τ19，τ20，τ21，τ22}.類似地，w選擇其quorum 為第 6 個(gè)，也即Q6={τ6，τ12，τ17，τ21，τ24，τ26，τ28}.u，v和w將其所選的 quorum 分別告知對(duì)方.那么，u和v之間就有τ16和τ202個(gè)公共時(shí)隙.由于節(jié)點(diǎn)間時(shí)鐘是異步的，以及在節(jié)點(diǎn)數(shù)量比較多時(shí)，難免會(huì)產(chǎn)生節(jié)點(diǎn)選擇quorum的沖突，如w可能選擇第3個(gè)quorum而和v產(chǎn)生沖突，所以此時(shí)需要重新選擇其quorum.為了算法的收斂，一個(gè)節(jié)點(diǎn)重新選擇quorum的次數(shù)是有限的.在這個(gè)算例中需要注意的是，盡管圖2(a)中大部分節(jié)點(diǎn)被選擇，但單個(gè)節(jié)點(diǎn)所選的活動(dòng)時(shí)隙數(shù)量并沒有如圖2(a)所示那么多.事實(shí)上，單個(gè)節(jié)點(diǎn)活動(dòng)時(shí)隙數(shù)量要小得多，如圖2(b)所示為u所選quorum，其占空比只有1/5.

算法1中給出的方法是收斂的，因?yàn)槠涫諗啃灾饕Q于該算法中的K值選擇，而K值一般為小于QS所含quorum數(shù)的正整數(shù)，是個(gè)較小的有限值.

3 SATA性能分析

SATA的性質(zhì)包括連通性以及異步時(shí)間分配的有效性.連通性是網(wǎng)絡(luò)中的基本特性，現(xiàn)有傳感網(wǎng)連通性研究主要集中在構(gòu)建網(wǎng)絡(luò)拓?fù)浜吐酚桑?－10］.但是節(jié)點(diǎn)工作在休眠機(jī)制下，拓?fù)浜吐酚裳芯恐兴@得的“連通”不能保證節(jié)點(diǎn)間相互通信.因此，之前有關(guān)傳感網(wǎng)的連通性是本文所考慮連通性的基礎(chǔ).在本文中的連通性是指在任意2個(gè)拓?fù)浠蚵酚上碌倪B通節(jié)點(diǎn)，在時(shí)間上的公共的活動(dòng)時(shí)隙.

通過SATA算法，即便節(jié)點(diǎn)間時(shí)鐘是異步的，相鄰的節(jié)點(diǎn)也能保證連通性不為零.以下引理給出了該連通性的量化結(jié)果.當(dāng)時(shí)鐘同步時(shí)，可以很容易地獲得引理2.如2個(gè)quorumQu和Qv分別包含第2行和第6行，在圖1(a)中，它們?cè)跁r(shí)隙τ17相交.因此它們物理上是連通的.

一個(gè)節(jié)點(diǎn)u很容易發(fā)生時(shí)鐘轉(zhuǎn)移的本地時(shí)間和準(zhǔn)確時(shí)間之差.因此，u和v之間的相對(duì)時(shí)間漂移是本文假設(shè)總是滿足tδ(u，v)＜+∞.當(dāng)節(jié)點(diǎn)間的時(shí)鐘是同步時(shí)，tδ(u，v)=0;當(dāng)節(jié)點(diǎn)間的時(shí)鐘是異步時(shí)，tδ(u，v)＞0.

引理2 當(dāng)節(jié)點(diǎn)間時(shí)鐘漂移是任意正值時(shí)，任何同屬一個(gè)QS的一對(duì)quorum一定有個(gè)公共活動(dòng)時(shí)隙.

證明 根據(jù)引理1，網(wǎng)格QS滿足旋轉(zhuǎn)封閉性.因此，任何2個(gè)quorumQu和Qv滿足

對(duì)于任意一對(duì)鄰居節(jié)點(diǎn)u和v，有相對(duì)時(shí)鐘漂移tδ(u，v)時(shí)，其相應(yīng)的每個(gè)節(jié)點(diǎn)所選擇的活動(dòng)時(shí)隙集合(也即該節(jié)點(diǎn)所選擇的quorum)也發(fā)生改變.不失一般性，Qv的旋轉(zhuǎn)表示為R(Qv，tδ(u，v)).因?yàn)镼S有選擇封閉性，即任意2個(gè)鄰居節(jié)點(diǎn)所選擇的quorum滿足式(2).對(duì)于i=0，1，…，m－1，Qu∩R(Qv，i)≠?，Qu，Qv∈Ω，并且v∈θu.因?yàn)閠δ(u，v)modm是正數(shù)并且小于m－1，而一個(gè)周期所包含的時(shí)隙為m個(gè).因而鄰居節(jié)點(diǎn)u和v是物理連通的.

計(jì)算在異步情況下任意2個(gè)鄰居節(jié)點(diǎn)之間所擁有的公共活動(dòng)時(shí)隙數(shù)量，也即計(jì)算R(Qv，tδ(u，v))∩Qu的勢(shì).根據(jù)文獻(xiàn)［11］的定理3和本文引理2，很容易得到

引理3 當(dāng)節(jié)點(diǎn)的需求能被完成時(shí)，同一個(gè)θu集合中所有節(jié)點(diǎn)的需求一定滿足其中C3(I)是依賴于干擾模型I的常量.

證明 當(dāng)沒有無(wú)線信道干擾存在時(shí)，θu中所有節(jié)點(diǎn)共享同一周期.所以考慮無(wú)線干擾時(shí)，本文用干擾模型I來(lái)模擬其干擾，為了避免干擾沖突而降低數(shù)據(jù)傳輸速率，每一個(gè)通信集只能在每C3(I)個(gè)周期中的某一個(gè)進(jìn)行通信.因而平均數(shù)據(jù)率是

減少每個(gè)節(jié)點(diǎn)的最大需求并非無(wú)限的，因?yàn)槊總€(gè)節(jié)點(diǎn)應(yīng)該在至少m個(gè)時(shí)間段內(nèi)保持活躍，以滿足旋轉(zhuǎn)封閉性.因此一個(gè)節(jié)點(diǎn)u的需求應(yīng)有一個(gè)下界，因?yàn)镼u包括行和1列，下界可以通過以下引理獲得.

引理4 當(dāng)Ωq滿足旋轉(zhuǎn)封閉性且m＞1，每個(gè)節(jié)點(diǎn)的需求須滿足

證明 任意一個(gè)節(jié)點(diǎn)u，Qu的勢(shì)為，根據(jù)文獻(xiàn)［11］，如果一個(gè)QS滿足旋轉(zhuǎn)封閉性，那么該QS中任何一個(gè)quorum的勢(shì)一定不小于所以，可以得到2.當(dāng)m=1，上面的不等式總能滿足，因?yàn)椋@里

使根據(jù)引理 4，因此有

4 實(shí)驗(yàn)設(shè)置與結(jié)果分析

本文構(gòu)建TelsoB節(jié)點(diǎn)實(shí)驗(yàn)平臺(tái)，平臺(tái)由100個(gè)節(jié)點(diǎn)構(gòu)成.同時(shí)，本文在TinyOS系統(tǒng)上實(shí)現(xiàn)SATA方法的編程，并就網(wǎng)絡(luò)吞吐量和數(shù)據(jù)包接受率(PRR)2個(gè)方面，與B-MAC進(jìn)行比較.

4.1 實(shí)驗(yàn)平臺(tái)設(shè)置

實(shí)驗(yàn)平臺(tái)中，100個(gè)節(jié)點(diǎn)被隨機(jī)地部署在室內(nèi)實(shí)驗(yàn)床上.每一個(gè)傳感器節(jié)點(diǎn)通過調(diào)節(jié)其內(nèi)置天線的傳輸功率，使得傳輸距離在10 cm以內(nèi).由此，節(jié)點(diǎn)在原始網(wǎng)絡(luò)中仍然可以通過多跳方式與周圍的節(jié)點(diǎn)建立通信.部署完畢后，開始實(shí)驗(yàn)，包括2個(gè)步驟:①所有的節(jié)點(diǎn)在開始時(shí)以100%的占空比進(jìn)行工作，在整個(gè)網(wǎng)絡(luò)中構(gòu)建一棵樹，由此每個(gè)節(jié)點(diǎn)獲得在樹中的編號(hào).② 采用SATA算法，每個(gè)節(jié)點(diǎn)根據(jù)其在樹中的位置和編號(hào)按照算法1選擇它們的quorum.在B-MAC方法中，將占空比設(shè)置為20%.在SATA方法中，每個(gè)周期包含100個(gè)時(shí)隙，每個(gè)時(shí)隙分別設(shè)置為1和2 s.每個(gè)節(jié)點(diǎn)采樣數(shù)據(jù)的時(shí)間間隔分別為 10，50，100，200，300，500，800，1 000，1 500和2 000 ms.每個(gè)采樣數(shù)據(jù)的大小為104 bit.

4.2 性能比較

圖3分別給出了在SATA和B-MAC兩種情形下的網(wǎng)絡(luò)吞吐量實(shí)驗(yàn)結(jié)果.在圖3(a)和圖4(a)中，每隔時(shí)隙是500 ms;在圖3(b)和圖4(b)中，每隔時(shí)隙為1 000 ms.從圖3中不難發(fā)現(xiàn)，當(dāng)數(shù)據(jù)產(chǎn)生間隔由小變大時(shí)，網(wǎng)絡(luò)吞吐量由小變大，再由大變小.當(dāng)數(shù)據(jù)產(chǎn)生間隔為500 ms時(shí)，SATA獲得吞吐量達(dá)到最大值0.91 Kbit/s;而當(dāng)數(shù)據(jù)產(chǎn)生間隔為800 ms時(shí)，B-MAC獲得吞吐量達(dá)到最大值0.53 Kbit/s.在圖3(a)和(b)的2種情況下，SATA所獲得吞吐量在每個(gè)數(shù)據(jù)產(chǎn)生間隔情況下都大于B-MAC.產(chǎn)生圖3中實(shí)驗(yàn)結(jié)果的原因是因?yàn)椋贐MAC方法中，節(jié)點(diǎn)需要在傳輸每一個(gè)數(shù)據(jù)包時(shí)進(jìn)行信道的競(jìng)爭(zhēng)和節(jié)點(diǎn)間的通信協(xié)調(diào)，因而許多時(shí)間被浪費(fèi).另外，當(dāng)時(shí)隙變大時(shí)，即圖3(a)和(b)進(jìn)行橫向比較時(shí)，SATA和B-MAC的吞吐量都有所下降.由于時(shí)隙有些過大，活動(dòng)時(shí)隙的時(shí)間未被充分利用，從而當(dāng)時(shí)隙變大時(shí)，更多時(shí)間沒有得到有效的利用，因而網(wǎng)絡(luò)吞吐量下降.同時(shí)發(fā)現(xiàn)SATA所獲得的網(wǎng)絡(luò)吞吐量在時(shí)隙變化的情況下，變化并不很明顯，但是這對(duì)B-MAC所獲得吞吐量的影響則很大.

圖3 吞吐量比較

圖4 數(shù)據(jù)包接受率比較

數(shù)據(jù)包接收率反映了一個(gè)網(wǎng)絡(luò)中的信道利用率.采用B-MAC和SATA算法，數(shù)據(jù)包接收率隨著數(shù)據(jù)間隔變大而變大.當(dāng)數(shù)據(jù)產(chǎn)生間隔比較小(小于300 ms)時(shí)，B-MAC和SATA的數(shù)據(jù)包接受率都不高.但導(dǎo)致這2個(gè)協(xié)議在此時(shí)數(shù)據(jù)包接受率不高的原因并不相同.在B-MAC方法中，數(shù)據(jù)產(chǎn)生間隔小的時(shí)候，數(shù)據(jù)包產(chǎn)生速率快，節(jié)點(diǎn)間信道競(jìng)爭(zhēng)的激烈程度加大，導(dǎo)致數(shù)據(jù)包丟失概率增大.而在SATA方法中，數(shù)據(jù)包的丟失是由于每個(gè)節(jié)點(diǎn)活動(dòng)時(shí)隙的數(shù)量不能滿足數(shù)據(jù)包傳輸所需時(shí)間的要求.當(dāng)數(shù)據(jù)產(chǎn)生間隔增加時(shí)，B-MAC中節(jié)點(diǎn)信道競(jìng)爭(zhēng)有所緩解，但是依然存在，所以在數(shù)據(jù)產(chǎn)生間隔大于300 ms時(shí)，其數(shù)據(jù)包接受率比SATA要低.

5 結(jié)語(yǔ)

本文設(shè)計(jì)了一個(gè)異步時(shí)間分配方法SATA，在節(jié)點(diǎn)間時(shí)鐘不同步的情況下，該方法無(wú)需同步機(jī)制也能保證相鄰節(jié)點(diǎn)間能夠通信，確保物理連通，完成通信任務(wù).同時(shí)，SATA能盡量減少節(jié)點(diǎn)的活動(dòng)時(shí)間和增加節(jié)點(diǎn)的休眠時(shí)間，從而節(jié)省能量.并且，本文構(gòu)建了TelosB節(jié)點(diǎn)組成的無(wú)線傳感網(wǎng)真實(shí)平臺(tái)，通過編寫TinyOS程序?qū)崿F(xiàn)了SATA方法，而B-MAC協(xié)議的程序是TinyOS系統(tǒng)自帶的，所以在TinyOS編程時(shí)只是調(diào)節(jié)其占空比.理論分析表明，SATA在時(shí)鐘異步情況下具有無(wú)需同步的優(yōu)點(diǎn)，且可以按需調(diào)節(jié)節(jié)點(diǎn)的占空比.實(shí)驗(yàn)結(jié)果表明，SATA比B-MAC協(xié)議有更高的吞吐量和更低的能耗.

［1］Mo Lufeng，He Yuan，Liu Yunhao，et al.Canopy closure estimates with greenorbs:sustainable sensing in the forest［C］//Proceedings of the7th ACM Conference on Embedded Networked Sensor Systems. Berkeley， CA，USA，2009:99－112.

［2］Kredo K，Mohapatra P.Medium access control in wireless sensor networks［J］.Elsevier Computer Networks，2007，54(4):961－994.

［3］Maróti M，Kusy B，Simon G，et al.The flooding time synchronization protocol［C］//ACM Sensys04'.Baltimore，Maryland，USA，2004:39－49.

［4］Polastre J，Hill J，Culler D.Versatile low power media access for wireless sensor networks［C］//ACM Sensys04'.Baltimore，Maryland，USA，2004:3－5

［5］Dam T V，Langendoen K.An adaptive energy-efficient MAC protocol for wireless sensor networks［C］//ACM Sensys03'.Los Angeles，USA，2003:171－180.

［6］Jian Ying，Chen Shigang.Can CSMA/CA networks be made fair?［C］//Proceedings of ACM Mobi Com08'.San Francisco，USA，2008:235－246.

［7］Malkhi D，Reiter M.Byzantine quorum systems［J］.Distributed Computing，1998，11(4):203－213.

［8］Jiang J R，Tseng Y C，Hsu C S，et al.Quorum-based asynchronous power-saving protocols for IEEE 802.11 ad hoc networks［J］.Mobile Networks and Applications，2005，10(1):169－181.

［9］Wu Shanhung，Chen Mingsyan，Chen Chungmin.Fully adaptive power saving protocols for ad hoc networks using the hyper quorum system［C］//The28th International Conference on Distributed Computing Systems.Beijing，China，2008:785－792.

［10］Chaporkar P，Sarkar S，Shetty R.Dynamic quorum policy for maximizing throughput in limited information multiparty MAC［J］.IEEE/ACM Transactions on Networking，2006，14(4):835－848.

［11］Bian Kaigui，Park J M，Chen Ruiliang.A quorumbased framework for establishing control channels in dynamic spectrum access networks［C］//Proceedings of ACM Mobi Com09'.Beijing，China，2009:25－36.

A scheme of asynchronization time assignment based on Quorum system in wireless sensor networks

Yang Lu

(School of Computer Science and Engineering，Southeast University，Nanjing 211189，China)
(Key Laboratory of Computer Network and Information Integration of Ministry of Education，Southeast University，Nanjing 211189，China)

In order to obtain fair channel access and to increase channel utilization in wireless sensor networks(WSNs)，a localized and on-demand scheme of asynchronization time assignment(SATA)is proposed.SATA is designed based on the Quorum system(QS).A QS is constructed firstly.SATA can determine a proper number of active time slots in QS according to the node's communication demand and inform the node's neighboring nodes in order to eliminate the channel competition.So each pair of neighboring nodes has sufficient rendezvous active time slots to finish the communication using SATA.The QS using SATA is rotation closed，so even under asynchronization of nodes'clocks and without adoption of time synchronization protocol，SATA can still ensure the network connectivity.The theoretical and experimental results show that SATA can increase the channel utilization，save energy and increase network throughput.

asynchronous time assignment;duty cycle;Quorum systems;wireless sensor networks

TP393

A

1001－0505(2013)01-0006-06

10.3969/j.issn.1001－0505.2013.01.002

2012-05-28.

楊璐(1980—)，女，博士生，yanglu@seu.edu.cn.

楊璐.一種基于Quorum系統(tǒng)的異步傳感網(wǎng)局部時(shí)間分配算法［J］.東南大學(xué)學(xué)報(bào):自然科學(xué)版，2013，43(1):6－11.［doi:10.3969/j.issn.1001－0505.2013.01.002］