楊 璐

(東南大學計算機科學與工程學院，南京 211189)

(東南大學計算機網(wǎng)絡和信息集成教育部重點實驗室，南京 211189)

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

楊 璐

(東南大學計算機科學與工程學院，南京 211189)

(東南大學計算機網(wǎng)絡和信息集成教育部重點實驗室，南京 211189)

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

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

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

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

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

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

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

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

圖1 網(wǎng)格QS

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

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

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

2 SATA算法設計

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

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

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

算法1 Quorum選擇方法(SATA)

圖2 quorum選擇示例

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

算法1中給出的方法是收斂的，因為其收斂性主要取決于該算法中的K值選擇，而K值一般為小于QS所含quorum數(shù)的正整數(shù)，是個較小的有限值.

3 SATA性能分析

SATA的性質(zhì)包括連通性以及異步時間分配的有效性.連通性是網(wǎng)絡中的基本特性，現(xiàn)有傳感網(wǎng)連通性研究主要集中在構建網(wǎng)絡拓撲和路由［9－10］.但是節(jié)點工作在休眠機制下，拓撲和路由研究中所獲得的“連通”不能保證節(jié)點間相互通信.因此，之前有關傳感網(wǎng)的連通性是本文所考慮連通性的基礎.在本文中的連通性是指在任意2個拓撲或路由下的連通節(jié)點，在時間上的公共的活動時隙.

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

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

引理2 當節(jié)點間時鐘漂移是任意正值時，任何同屬一個QS的一對quorum一定有個公共活動時隙.

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

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

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

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

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

減少每個節(jié)點的最大需求并非無限的，因為每個節(jié)點應該在至少m個時間段內(nèi)保持活躍，以滿足旋轉封閉性.因此一個節(jié)點u的需求應有一個下界，因為Qu包括行和1列，下界可以通過以下引理獲得.

引理4 當Ωq滿足旋轉封閉性且m＞1，每個節(jié)點的需求須滿足

證明 任意一個節(jié)點u，Qu的勢為，根據(jù)文獻［11］，如果一個QS滿足旋轉封閉性，那么該QS中任何一個quorum的勢一定不小于所以，可以得到2.當m=1，上面的不等式總能滿足，因為，這里

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

4 實驗設置與結果分析

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

4.1 實驗平臺設置

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

4.2 性能比較

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

圖3 吞吐量比較

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

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

5 結語

本文設計了一個異步時間分配方法SATA，在節(jié)點間時鐘不同步的情況下，該方法無需同步機制也能保證相鄰節(jié)點間能夠通信，確保物理連通，完成通信任務.同時，SATA能盡量減少節(jié)點的活動時間和增加節(jié)點的休眠時間，從而節(jié)省能量.并且，本文構建了TelosB節(jié)點組成的無線傳感網(wǎng)真實平臺，通過編寫TinyOS程序實現(xiàn)了SATA方法，而B-MAC協(xié)議的程序是TinyOS系統(tǒng)自帶的，所以在TinyOS編程時只是調(diào)節(jié)其占空比.理論分析表明，SATA在時鐘異步情況下具有無需同步的優(yōu)點，且可以按需調(diào)節(jié)節(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)局部時間分配算法［J］.東南大學學報:自然科學版，2013，43(1):6－11.［doi:10.3969/j.issn.1001－0505.2013.01.002］