無線傳感器網絡ＱｏＳ路由研究進展

摘要：傳統網絡中的服務質量(quality of service，QoS)路由協議很難直接有效地應用到無線傳感器網絡中，因此人們針對無線傳感器網絡提出了一些新的QoS路由協議。首先探討了無線傳感器網絡中QoS路由協議的一些特點，分析了設計QoS路由協議所面臨的挑戰；然后著重分析了當前提出的一些QoS路由協議的QoS機制、特點以及優缺點，并對這些路由協議進行了分類和比較；最后總結了QoS路由協議未來的研究策略和發展趨勢。

關鍵詞：無線傳感器網絡； 服務質量； 服務質量路由協議； 服務質量支持

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2008)05-1304-05

無線傳感器網絡作為一種有廣泛應用前景的新型信息獲取和處理技術，引起了國內外學術界和產業界的高度關注 [1~5]。近幾年來，WSNs在各個研究領域都取得了不同程度的進展。

由于設計目標不同，WSNs與傳統網絡有很大的差異：a)傳統網絡主要是作為一種通信的方式來設計的，它們側重于考慮整體網絡上的信息傳輸；WSNs主要是作為一種信息獲取的方式，它們把更多的注意力放在了資源有限的節點上和數據處理上。b)WSNs一般與應用緊密相關、以數據為中心[5]。其特點包括：節點更多、規模更大、網絡生命期更短；在節點上的計算、存儲、通信能力更有限；網絡負載、能耗更加不均衡等。這些特點使得傳統網絡中的QoS路由協議很難直接有效地應用到WSNs中，因此WSNs迫切需要一種適合它的新型QoS路由協議。

目前，研究人員針對各種應用陸續提出了一些支持QoS的機制和策略[6~20]，這些機制和策略涉及到各個方面。它們包括QoS的模型、體系結構、路由協議、MAC協議、控制機制、QoS支持的整合以及服務區分等。本文主要針對QoS路由協議進行研究，分析和總結了當前比較典型的QoS路由協議的核心機制和特點，指出了未來的研究策略及發展趨勢。這樣做的目的在于更好地理解WSNs QoS路由協議，為QoS路由協議的進一步研究提供參考。

1無線傳感器網絡中QoS路由協議

QoS路由協議也稱為QoS感知的路由協議或提供QoS支持的路由協議。WSNs中QoS路由協議的主要目標一般有三個：找到滿足QoS需求的路由；盡量提高網絡資源的利用率；節省能量，提高網絡生存時間。第一個目標要求在多約束條件下計算可行路徑；第二個目標要求在多條可行路徑中進一步優化，優化的方式通常是首先設計cost函數，然后求解函數值最優的可行路徑；第三個目標是由WSNs的節點能量有限的特點決定的，也是需要優先考慮的目標。

作為在網絡層提供QoS支持的載體，QoS路由協議的好壞對WSNs的性能有重要影響。在WSNs體系結構中，網絡層是提供QoS支持的重要組成部分。這里主要有兩個原因[21]：

a)在網絡層可以提供端到端的可靠穩定的QoS保證。雖然WSNs由于本身的特點提供硬實時的QoS保證很困難，但可以通過路由協議來實現軟實時的QoS保證[22]。另外在網絡層提供的多路徑路由機制是提高數據傳輸可靠性和實現網絡負載平衡的有效手段。由于WSNs一般規模很大，節點的傳輸功率有限，WSNs的路由協議中多采用多跳路由來節省能量，從而達到能量有效的目的。

b)處于MAC層和應用層之間的網絡層是上下兩個層次的有機結合點。MAC層只有點到點的單跳概念，而應用層也只關心具體應用的信息而不去關心網絡的狀況。因此，處在中間的網絡層就起到一個橋梁的作用，它可以把應用層的QoS參數映射到MAC層的參數上，同時也可以把MAC層對應用層的反饋信息映射到應用層參數上。

根據上述分析，本文提出了一個簡單的QoS路由協議的分析模型，如圖1所示。模型左邊是QoS路由協議的主要設計目標；右邊則是一個好的QoS路由協議應考慮的一些條件。

2設計無線傳感器網絡QoS路由協議所面臨的挑戰

WSNs自身的特點決定了設計QoS路由協議將面臨很大的挑戰，通常的挑戰分析如下[23~25]：

a)無統一的網絡標志。WSNs的規模一般很大，并且是以數據為中心，很難為整個網絡分配統一的邏輯地址。因此路由協議一般只能采用分布式策略，通過局部拓撲信息來構建并維護路由。

b)以數據為中心。與以地址為中心的傳統通信方式不同，以數據為中心的WSNs的基本思想是把傳感器視為感知數據源，把傳感器網絡視為感知數據庫，把數據管理和處理作為網絡的應用目標。因此在設計QoS路由協議時需要新的設計思路。

c)數據高度冗余。為了降低開銷和節省能量，要求中間節點在轉發時進行數據融合，但QoS數據流的融合相對復雜。比如圖像數據流和視頻數據流本身的比較就是一種很耗費計算資源和能量資源的事情。因此在源節點對數據流進行簡單的聚合處理是有必要的。

d)資源嚴格受限。包括能量、計算能力、存儲能力、傳輸功率等，要求路由算法盡量簡單有效并能夠在網絡整體上達到節能，延長網絡的生存時間，必要時還需要提供資源管理機制。

e)帶寬限制。特別是在上傳大量實時數據流的應用（圖像/視頻）中，帶寬的有效利用成為亟待解決的問題。f)能量—延時權衡。由于傳感器節點的傳輸功率與距離的平方成比例，為節省能量，一般采用多跳的方式傳輸數據；但跳數越多，數據傳輸的延時越大。因此應根據具體的實時性需求尋找最合適的權衡。

g)緩沖區大小限制。有限的緩沖區大小可能會增加傳輸的延時。網絡中一般存在多種分組類型。節點的緩沖區可以優先轉發實時需求較高的分組，而且充足的緩沖區大小可以提高數據融合的效率。

h)特定應用限制。特定應用中不僅要考慮路由算法的適用性和計算復雜性，還需考慮QoS參數之間以及QoS參數和能量之間明確的權衡。

i)對多種業務的QoS支持。隨著應用的深入，網絡中可能會同時存在多種應用，這些不同的應用也可能會有不同的QoS需求，這勢必會增加協議的復雜性，給QoS路由協議的設計帶來新的挑戰。

3典型QoS路由協議的分析

下面將對當前提出的一些典型無線傳感器網絡QoS路由協議進行研究，并對其QoS機制、特點和優缺點進行分析。

1)SAR(sequential assignment rounting，有序分配路由）[9] SAR是第一個基于WSNs提供QoS保證的路由協議，它基于樹結構創建多條從源節點到達sink節點的路徑，創建路徑時考慮節點的延時、丟包率等QoS參數以及最大數據傳輸能力;各個節點反向建立了到sink節點的具有不同QoS參數的多條路徑；源節點發送數據時根據路徑評價和數據分組包優先級確定傳輸路徑，選擇一條或多條路徑進行傳輸。它的優點是結合路徑能耗和數據分組包優先級來評估QoS度量；缺點是源節點需要保存到達sink節點的路由信息，且路由信息維護、節點QoS參數與能耗信息的更新均需較大開銷。

2)SPEED[10]SPEEDS協議的設計目標是能夠提供三種端到端的軟實時通信服務，即實時單播、實時區域多播和實時區域任播。節點首先通過與鄰節點交換鏈路傳輸延遲，利用延遲估計機制得到網絡負載情況，并判斷網絡是否發生擁塞；然后利用SNGF(stateless non－deterministic geographic forwarding)算法來選擇滿足傳輸速率要求的下一跳節點；當SNGF路由算法中找不到滿足傳輸速率的下一跳節點時，則通過鄰居反饋機制（neighborhood feedback loop，NFL）保證網絡傳輸速率在一個全局定義的傳輸速率閾值之上，其結構如圖2所示。同時SPEED協議還通過反向壓力路由變更機制來避免擁塞和路由空洞，使節點重新選擇合適的下一跳路由。由于整個網絡只能設置一個全局的傳輸速率閾值，不能提供多種業務流的實時需求。

節點首先檢查到達數據分組的類型并將其放到相應隊列中；觀測節點計算所有可選路徑的延遲，根據QoS需求確定帶寬比例取值；調度器則根據帶寬比例參數決定等待分組的傳輸次序。EQR可為實時業務提供一定的QoS保證，也可避免因實時業務流量劇增而嚴重影響非實時通信的吞吐量。然而EQR采用了集中式路由策略，源節點或觀測節點需要保留全網狀態信息，包括網絡拓撲和路徑代價等。雖然簡化了中繼節點的算法實現，但在大規模網絡部署環境下，協議開銷和性能都會迅速惡化。EQR節點隊列模型如圖3所示。

5)QoS－GBP [13]該協議通過基于幾何學的局部決定轉發機制來優化網絡中廣播的數量，達到通信開銷與延時之間的權衡以及節省能量的目的。協議假定每個節點都知道自己的位置，通過規則六邊形的有效覆蓋性質來確定最少的活動節點，如圖4所示。其中六邊形的頂點表示節點，邊長表示節點的通信半徑。每個節點在不同方向上確定最優的轉發位置（稱為戰略位置）來減少廣播的數量。網絡中的節點假定已獲得一跳鄰節點的位置信息，每個廣播分組的頭部包含兩個位置域參數L1和L2以及戰略位置附近的節點列表。其中，L1表示一個節點的位置；L2表示這個節點下一跳節點的位置，源節點把L1和L2加入到自己的位置（SX，SY）中，選擇戰略位置發送分組。為避免兩個距離很近的鄰節點相互轉發，協議設置了一個門限值Th。如果鄰節點之間的距離dm＜Th，則相互不轉發。QoS-GBP為避免重復轉發相同的分組，通常節點在一個延時后決定是否轉發分組，因此該協議實際上是用增加傳播延時的代價來換取較優的傳播開銷。

6)EQoS [14]這是一個以覆蓋率為主要的QoS參數，同時考慮負載均衡、延時和開銷的能量感知路由協議，支持同構和異構的WSNs。EQoS主要分為兩個階段：第一個階段需要建立一個虛擬的通信框架來確定網絡中節點的位置信息。在異構網絡中，一部分節點為增強型節點，具有較多的資源和GPS設備的支持，這些節點作為網絡中的位置參考節點，其他普通節點根據這些參考節點和局部定位算法得到自己的大致位置信息。同構網絡中的節點則要通過局部定位獲得位置信息。第二個階段是在第一個階段的基礎上，通過一個分布式的算法關閉冗余節點得到滿足一定覆蓋率的最小節點子集。該協議具有天然的分布式特性，擴展性好。協議中如果一個節點檢測到其他節點已經發送過相同的冗余信息，則該節點進入休眠狀態。這種頻繁的休眠與喚醒需要很大的開銷[19]。

7)MCBR [15]MCBR是一個基于約束的消息驅動路由協議，采用元路由策略通過消息機制在應用層提供QoS支持。它與一般路由協議的區別是，通過消息規范機制把選路目的、路由約束和選路目標明確地從路由策略中分離開，以便在路由協議中應用多種路由策略。這里的選路目的是指一條路由上各個節點屬性的約束集。路由約束一般是局部的路由約束條件，像如何避開擁塞、低能量的節點等。選路目標是路由選擇的指標，如最短路徑、最佳連通度、最小擁塞等。MCBR實際上是一個協議框架，框架內各種路由策略的適用范圍和性能還需作更深入的研究。

8)MMSPEED [16]這是一個在SPEED協議基礎上提出的基于區分優先級服務的路由協議，提供實時性和可靠性的QoS保證。MMSPEED通過多條路徑來實現數據分組的可靠傳輸，通過多個全局的分組傳輸速率來保證實現實時需求。該協議采用帶有動態補償的局部地理轉發機制來彌補僅靠局部信息決策所帶來的差錯。如果中間節點感知到數據分組以目前的速率無法滿足軟實時保證，該節點就把數據分組的傳輸速率調節到更高的級別。該協議的優點是可以滿足多種業務流的實時性和可靠性保證。缺點是算法相對復雜，能量消耗太大；另外協議的實時保證需要MAC層的優先級區分機制來支持，每一種速率值都要映射在MAC層的優先級分類中，如圖5所示，因此網絡中的開銷很大。

9)OEDSR [17]這是一個應用于目標監測、以節點能量消耗和端到端傳輸延時為鏈路代價建立最佳路由的QoS路由協議。它采用基于簇的分層路由結構，節點監測到的信息先傳到簇頭（CH），再由簇頭經多跳傳送到基站（BS）。簇頭根據式(3)選取。其中：Ern表示節點的剩余能量；S(n)表示節點監測到目標的屬性值。因此剩余能量越多、距離目標越近的節點越容易成為簇頭。節點根據鏈路代價選取下一跳中繼節點，鏈路代價如式（4）所示。其中：delay表示任意兩個節點之間端到端的延時；dist表示目的節點到基站的距離。該協議能夠保證源節點到基站的最小延時和能量有效；缺點是在選擇中繼節點時，簇頭需要向通信范圍內所有節點廣播Hello分組，并需要節點發送應答分組，開銷較大。

10)Laura Savidge等人[18]提出的基于QoS的地理位置路由協議(QGR)在WSNs中周期性地上傳監測到的圖像信息是一個典型的事件驅動應用，大量同時上傳的大尺寸數據分組可能會降低網絡的吞吐量，導致較長的傳輸延時。QGR的目標就是解決在低帶寬的WSNs環境下實現大量周期性上傳的數據分組端到端的延時和盡力而為的QoS支持。為實現這一目標，該協議引入了兩種機制：在路由候選中加入基于隊列的代價函數；為不同的數據分組類型設置相應的優先等級。協議把網絡中的數據類型分為周期發送的低帶寬數據和事件驅動的高帶寬數據兩類。節點的隊列緩沖區根據數據類型也相應地分成兩類。隊列模型如圖6所示。假設節點轉發一種數據的概率為p，則同時轉發另一種數據的概率為1-p。該協議采用基于角度方位信息的定位策略，有效地節省了能量。但代價函數的計算特別是位置代價的計算相對復雜。

11)ReInForM[19]ReInForM是一個提供可靠數據傳輸的多路徑路由協議，考慮可靠性需求、信道質量以及傳感器節點到sink節點的跳數。計算出傳輸路徑數后，源節點在鄰節點中選擇下一跳節點作為轉發路徑。鄰節點根據與源節點的跳數比較被分為跳數相同、跳數少1和跳數多1三類，分別用H0s、H-s和H+s表示。源節點在H-s中選擇一個作為下一跳節點；其他中間節點采用與源節點相同的方式選擇自己的下一跳節點，直到數據到達sink節點。該協議由于需要通過sink節點的更新消息和鄰節點來獲得到達sink節點的跳數，不適合大規模的傳感器網絡。

(12)ADPROC [20]ADPROC是一個路由協議棧，其基本思想是在協議棧中加載不同的路由算法以滿足多種優先級的數據傳輸和QoS支持。對于擁有較高優先級和嚴格QoS需求的數據使用短快的路由；對于低優先級的數據則使用能量有效的路由。在滿足高優先級數據的路由算法中，節點需要時刻維持從源節點到目的節點的最短路由，當路由因為拓撲變化而失效，則需重新計算并保存在節點上。因此在大規模的網絡或拓撲變化頻繁的網絡中維護開銷太大。另外協議棧中各種算法的整合和協作還需作進一步的研究。

4QoS路由協議的分類和比較

由于WSNs具有與應用高度相關的特點，現有的大部分QoS路由協議也都是基于特定應用提出來的，很難說哪個路由協議更好。為了便于分析，本文采取列表的方式對這些路由協議進行分類和總結，如表1所示。

5結束語

到目前為止，提出的這些無線傳感器網絡QoS路由協議距離真正的實現和應用還需要一段時間。一方面這些路由協議除了在算法上需要繼續優化外，還需要做更多的實物實驗；另一方面則需要考慮更多工程上的細節和特定應用的需要。從上述QoS路由協議的分析來看，實時性(delay)和可靠性(reliability)是主要的QoS需求參數，傳統網絡中的QoS度量，如開銷、丟包率、帶寬和數據吞吐量則根據需要作為補充。隨著新應用的挖掘，必將出現新的QoS需求，因此QoS路由協議的研究還有待深入。通過深入理解現有的各種QoS路由協議的QoS機制和特點，為QoS路由協議的進一步研究提供參考，這也是本文的目的所在。

通過對當前的多種QoS路由協議進行分析與總結，進一步給出一些QoS支持未來的研究策略與發展趨勢：

a)WSNs的QoS支持需要一個更廣泛的概念。WSNs中的QoS已不再局限于傳統通信網絡中的QoS概念，還應根據具體的應用定義合適的QoS參數；另外QoS參數之間以及QoS參數和能量之間應有明確的權衡，不能過于追求優化問題的最優解。

b)為各種不同類型的應用建立QoS框架或標準，以致力于研究的規范性和工程上的可行性；本質上，WSNs的QoS需要一個系統的理論，這種理論區別于傳統的QoS。

c)應該更多地考慮QoS算法在工程上的可行性。到目前為止，大部分提出的QoS算法還只限于學術范圍的研究，沒有進入實際應用。因此應更多地考慮工程中的應用細節，如能否從網絡中獲得算法所需要的一些參數，能否在盡可能不改變網絡現有結構的前提下投入應用等。

d)QoS算法應盡量簡單有效，不能讓QoS算法本身的計算耗費太多的資源；另外算法應該是可擴展和快速收斂的。

e)多媒體流的QoS研究[26，27]。隨著單個傳感器節點性能的提高，WSNs被逐漸應用到圖像視頻等多媒體數據采集上，這一應用具有廣闊的前景。多媒體流的數據分組比一般的數據分組大，而且有嚴格的實時需求，這些挑戰使得多媒體流的QoS逐漸成為一個新的研究熱點。

f)綜合網絡中的QoS研究。目前，WSNs與基于IPv6的IP網絡的結合問題已經成為一個研究熱點。例如在城市全景信息感應系統中，智能家庭可以作為其中重要的一部分，而對于一個有幾百萬人口的城市，如果將來全部實現家居智能化，至少需要幾十萬的地址來區分不同的家庭，這樣才能在家庭網絡發出安全警報(如火警)的情況下提高應急能力。這樣的網絡規模對于WSNs來說是無法處理的，而IPv6為此類應用提供了可行性。這種綜合網絡中的QoS問題除了WSNs QoS本身的問題外，還要考慮QoS數據流的兼容和轉換問題。事實上，IPv6的本身具有很好的QoS機制，如數據包頭的流標記和流類別字段，這為兩種網絡的QoS合作提供了基礎。

參考文獻：

[1]AKYILDIZ L F， SU Wei－lian， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，40(8):102－114.

[2]任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14(7):1282-1291.

[3]崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展，2005，42(1):163－174.

[4]NICULESCU D， AMERIC N L. Communication paradigms for sensor networks[J]. IEEE Communications Magazine， 2005，43(3): 116－122.

[5]李建中，李金寶，石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報，2003，14(10):1717-1727.

[6]FELEMBAN E. Probabilistic QoS guarantee in reliability and timeliness domains in wireless sensor networks[C]//Proc of IEEE INFOCOM. 2005:2646-2657.

[7]DELICATO F C， PIRES P F ，RUST L， et al. Reflective middleware for wireless sensor networks[C]//Proc of the 20th Annual ACM Symposium on Applied Computing. New York: ACM Press， 2005.

[8]FROLIK J. QoS control for wireless sensor networks[C]//Proc of Wireless Communication and Networking Conference. Atlanta:[s.n.]， 2004.

[9]SOHRABI K， GAO J， AILAWADHI V， et al. Protocols for self-organization of a wireless sensor network[J]. IEEE Personal Communications， 2000，7(5): 16-27.

[10]HE Tian， STANKOVIC J， LU Chen－yang， et al. SPEED: a stateless protocol for real－time communication in sensor networks[C]//Proc of the 23rd Int’l Conference on Distributed Computing Systems. Wa-shington DC: IEEE Computer Society， 2003:46-55.

[11]AKKAYA K， YOUNIS M. An energy－aware QoS routing protocol for wireless sensor networks[C]//Proc of IEEE Workshop on Mobile and Wireless Networks. Piscataway: IEEE， 2003:710-715.

[12]毛鶯池，龔海剛，劉明，等.ELIQoS:一種高效節能、與位置無關的傳感器網絡服務質量協議[J].計算機研究與發展，2006，43(6):1019-1026.

[13]PARUCHURI V， DURRESI A， BAROLLI L， et al. QoS-energy aware broadcast for sensor networks[C]//Proc of the 8th International Symposium on Parallel Architectures， Algorithmsand Networks. Washington DC: IEEE Computer Society， 2005:524-529.

[14]SANLI H O， CAM H ， CHENG Xiu－zhen. EQoS: an energy efficient QoS protocol for wireless sensor networks[C]//Proc of Western Simulation Multi Conference. San Diego:[s.n.]， 2004.

[15]ZHAN G Ying， FROMHERZ M. Message－initiated constraint－based routing for wireless Ad hoc sensor networks[C]//Proc of the 1st IEEE Consumer Communications and Networking Conference.Pisca-taway: IEEE， 2004:648-650.

[16]FELEMBAN E， LEE C G， EKICI E. MMSPEED: multipath multi－SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[J]. IEEE Trans on Mobile Computing， 2006，5(6):738-754.

[17]RATNARAJ S，JAGANNATHAN S，RAO V.OEDSR:optimized energy－delay sub－network routing in wireless sensor network[C]//Proc of IEEE International Conference on Networking， Sensing and Control. 2006:330-335.

[18]SAVIDGE L， LEE H， AGHAJAN H， et al. QoS－based geographic routing for event－driven image sensor networks broadband networks[C]//Proc of the 2nd International Conference on Broadband Networks. 2005:68-77.

[19]DEB B， BHATNAGAR S， NATH B. ReInForM: reliable information forwarding using multiple paths in sensor networks[C]//Proc of the 28th Annual IEEE Int’l Conf Local Computer Networks. Washington DC: IEEE Computer Society， 2003:406-415.

[20]GUNDAPPACHIKKENAHALLI K， ALI H H. ADPROC: an adaptive routing framework to provide QoS in wireless sensor networks[C]//Proc of the 24th IASTED International Conference on Parallel and Distributed Computing and Networks. Anaheim: ACTA Press， 2006:76-83.

[21]MISRA S， REISSLEIN M， XUE Guo－liang. A survey of multimedia streaming in wireless sensor networks[EB/OL].http://www.fulton.asu.edu/~mre/WSNstreaming.pdf.

[22]VERES A， CAMPBELLl A， BARRY M， et al. Supporting service differentiation in wireless packet networks using distributed control[J]. IEEE Journal on Selected Areas in Communications， 2001，19(10):2081-2093.

[23]YOUNIS M， AKKAYA K， ELTOWEISSY M， et al. On handling QoS traffic in wireless sensor networks[C]//Proc of the 37th Annual Hawaii International Conference. 2004.

[24]WANG Yuan－li， LIU Xiang－hui， YIN Jian－ping. Requirements of quality of service in wireless sensor network[C]//Proc of Internatio-nal Conference on Systems and International Conference on Mobile Communications and Learning Technologies. Washington DC: IEEE Compter Society， 2006:116.

[25]AL－KARAKI J N， KAMAL A E. Routing techniques in wireless sensor networks: a survey[J]. Wireless Communications， 2004，11(6):6-28.

[26]MA Hua－dong， LIU Yong－he. Correlation based video processing in video sensor networks[C]//Proc of International Conference on Wireless Networks， Communications and Mobile Computing. Piscataway: IEEE Press， 2005:987-992.

[27]TAO Dan， MA Hua－dong， LIU Yong－he. Energy－eficient cooperative image processing in video sensor networks [C]//Proc of Pacific－Rim Conf on Multimedia.Berlin:Springer－Verlag，2005:572-583.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”