無線傳感器網絡中基于尺度的協同中繼跨層QoS路由算法

徐 楠，孫亞民，于繼明，王 華

(1.南京理工大學計算機科學與技術學院，南京 210094;2.浙江工業大學計算機科學與技術學院，杭州 310014;3.山東大學計算機科學與技術學院，濟南 250023)

無線傳感器網絡中基于尺度的協同中繼跨層QoS路由算法

徐 楠1，孫亞民1，于繼明2，王 華3

(1.南京理工大學計算機科學與技術學院，南京 210094;2.浙江工業大學計算機科學與技術學院，杭州 310014;3.山東大學計算機科學與技術學院，濟南 250023)

提出了一種基于尺度的協同中繼自主轉發跨層QoS路由算法(MCRICQR)。節點根據能量、信道、擁塞以及與匯點的距離等綜合因素形成一個選擇度量，度量最大的節點根據自己所處狀態自主選擇直接轉發、中繼轉發以及躍進轉發數據包。仿真結果表明，該算法能根據網絡狀況及時轉發數據，提高網絡可靠性，對網絡負載進行均衡，提高網絡吞吐量和能量效率，從而延長網絡壽命，保障了無線傳感器網絡的QoS需求。

服務質量;跨層設計;協同中繼;自主轉發;無線傳感器網絡

1 前言

無線傳感器網絡(wireless sensor network，WSN)是一種無基礎設施、多跳、自組織的網絡，網絡中的節點具有感知、收集、聚合、處理、轉發數據的功能，通過無線信道進行通信，可以廣泛地應用在軍事、環境、健康、家庭、空間探索、災難拯救和其他商業領域［1］。

無線介質的廣播特性允許多個節點接收和處理同一個傳輸的信號［2］，協同中繼就是利用這一特性，使節點協同通信，成功將信息發送到匯點。與直接傳輸和傳統的經典中繼相比，它能明顯降低獲得一定的中斷概率所需要的信噪比(SNR)。由于無線鏈路造成的獨特問題、在無線鏈路上機會通信的可能性以及無線介質所提供的通信模式，激發人們進行跨層設計的嘗試。通過同時對網絡的多個層次進行優化控制，跨層設計可以大幅度提高網絡容量，減少干擾和功率消耗［3］。

2 系統模型

WSN節點可以用一個無向圖G(V，E)來表示。V表示節點集合，E表示邊的集合。節點u和v間存在邊(u，v)∈E，意味著u和v間存在一條可以互相通信的無線鏈路。

2.1 基本定義

定義1 虛擬自主轉發節點是這樣的節點集合U

定義2 下一跳可行自主轉發虛擬節點集合J。當一個節點i有DATA包要發送時，i就廣播一個RTS請求，其鄰居就會收到該廣播包，那些比節點i距離匯點更近，并且符合公式(1)的節點j的集合就形成下一跳可行自主轉發虛擬節點集合J，節點j會向節點i發送CTS。

定義3 虛擬中繼可行節點集合R。假定節點的i下一跳轉發節點是j，虛擬中繼可行轉發節點集是這樣的節點集合:節點r在下一跳轉發節點j的傳輸范圍之內，并收到來自節點i的一個RTS及一個DATA包，將該DATA包存儲，當下一跳節點j不能解碼數據包時，節點j會發一個“重新傳輸請求”(RREQ)控制包給節點i，偷聽到RREQ控制包的節點r的集合形成一個虛擬可行中繼節點集R。

定義4 虛擬可行躍進節點L。虛擬可行躍進節點屬于這樣的節點集合:偷聽到一個中繼節點傳輸的DATA包的節點，該節點從沒有收到這個DATA包的RTS，并能對所收到的DATA包進行正確解碼，比下一跳節點距離匯點更近的節點I所形成的節點集合L。

2.2 鏈路和網絡假設

網絡中所有節點具有自己的位置信息以及匯點sink的位置信息;除sink節點外，每個節點在協同將數據包從源傳輸到匯點的過程中，可以作為下一跳的轉發節點NHF(next_hop forwarding node)、中繼節點RFN(relay forwarding node)或作為躍進節點LPF(leapfrogging node)，在這里，我們稱這些符合條件的節點形成一個虛擬可行轉發節點集合。下一跳節點與傳統的方法相似，將數據包逐跳轉發。為了確保虛擬節點集合中最適合的節點選擇來轉發數據，符合條件的虛擬節點集合中的節點競爭作為NHF、RFN、LPF節點。節點的選擇和節點的角色分配過程是基于尺度來進行的。

假設有|V|個節點均勻地分布在整個無線傳感器網絡中。每個節點都安裝了一幅全向天線，這樣每個節點都可以從其他節點接收到信息，并且網絡中的所有節點都是工作在半雙工模式，即不能同時接收和發送。同時假設每個節點的背景噪聲是方差為σ2的高斯噪聲。每個節點接收采用最大比值合并和解碼中繼協議，即當節點正確接收信息后，才將信息轉發到下一跳節點，這樣每一條的信息傳輸都是可靠傳輸，可以避免錯誤信息被傳遞。MAC層協議利用帶RTS/CTS的CSMA協議。

信道模型。瑞利平坦衰落模型［4］:任何兩個距離為d的傳感器節點之間傳輸數據包輸入輸出關系建模:

式(2)中，α是無線信道的路徑損失指數，2≤α≤6;r［t］和 s［t］分別是復合的接收信號和發射信號，g［t］是描述衰落的信道增益，g［t］～ CN(0，1)，方差被歸一化為1;w［t］是均值為零的復合加性白高斯過程，波譜功率密度為 N0，w［t］～ CN(0，N0)。

式(3)中，ε0是初始能量;si是在時間i時無線收發器的狀態;εs是在狀態s的能量消耗。傳感器節點的無線收發器狀態可以是傳輸、發送、空閑。

3 MCRICQR算法

無線傳感器網絡中基于尺度的協同中繼自主轉發跨層QoS路由算法(metric－based cooperative relay initiative forwarding cross－ layer qos routing，MCRICQR)，與以前所提出的QoS路由算法最大的不同是:下一跳轉發節點的選擇由其通信范圍內節點所形成的虛擬可行轉發節點集合通過競爭決定，每個節點不用存儲鄰居節點的信息。即每個節點i根據自己當前的能量、信道狀況、擁塞情況(由和來共同確定)以及與匯點的距離來決定自己所扮演的角色，節點的角色可以是NHF、RFN、LPF，然后節點自主轉發數據。這樣，每個節點就不需要浪費寶貴的存儲空間來存儲鄰居節點信息。由于競爭是基于定時器時間的，可以減少信道爭用，提高信道利用率。此外，節點不用為維護路由等進行額外的能量開銷。

當節點i有數據包DATA要發送時，它首先廣播一個RTS控制信息包，該包包含的內容有節點i的位置、DATA包標識符以及響應CTS的持續時間。RTS包可以讓收到該包的節點用來作為鏈路質量指示器(RSSI)，計算瞬時信道增益 gi，j［t］，所有收到節點i的RTS包的節點根據公式(1)，同時滿足di，sink＜ dj，sink形成一個下一跳虛擬可行轉發節點集合J，集合J中的每個節點j根據公式(4)來計算尺度，根據公式(5)，選出NHF節點。

式(4)中，a，b，c為權重系數，一般設為常數。在t時刻，最佳下一跳轉發節點NHF為:

下一跳虛擬可行轉發集合中的每個節點j，計算尺度后，設置一個定時器的等待時間，該定時器與mj［t］成反比，定時器結束時，發送 CTS包響應該RTS包。當節點在定時器超時前聽到其他節點發送的CTS對同一個RTS響應，則它放棄競爭。這種競爭基于尺度，可以提高無線鏈路的利用率。節點i將數據轉發給贏得競爭的節點NHF。節點i忽略首次CTS到達后的所有針對該DATA的CTS包，其目的是為了避開隱藏終端的影響。

節點i收到節點NHF發來的 CTS后，就將DATA包發送給下一跳轉發節點NHF。如果NHF能夠成功地將DATA包接收并解碼的話，則NHF就向節點i發送一個ACK控制信息包，該控制信息包包括DATA包標識符等相關信息。由此可知，上一跳和下一跳節點間是基于RTS/CTS的交換。

如果節點NHF不能正確地解碼DATA包，則節點NHF就向節點i發出一個重新請求發送RREQ(該控制包也可以作為判斷NHF有無中繼節點的依據，當RREQ≥2時，存在中繼節點)，RREQ控制包攜帶的內容有:DATA包的標識符，下一跳節點的地理位置信息等。節點i收到RREQ包之后，就為該重傳包設置RREQ定時器，其值為NHF定時器值大小。當虛擬中繼可行集合R中的每個節點偷聽到RREQ后，計算瞬時信道增益，并根據計算尺度選擇公式(6)，競爭最佳中繼節點。根據公式(7)，可以找到RFN節點。虛擬可行中繼節點集合R中的每個節點設置一個計時器，該計時器與mr［t］成反比，定時器最先到期的節點就是RFN，RFN就向節點NHF發送DATA包。其他中繼節點聽到有DATA在傳送給NHF就放棄競爭。節點NHF成功收到DATA包后，就向節點i發送一個ACK控制包，節點i收到該ACK包后，就取消 RREQ定時器。節點NHF扮演節點i的角色轉發數據包。如果虛擬可行中繼節點集合為空，則上一跳節點i在設置的定時器時間過期時重傳該DATA包。

在t時刻，最佳中繼節點RFN為:

當節點RFN向節點NHF發送DATA包時，RFN的通信范圍內的節點也會偷聽到該DATA包。此時，若NHF節點還不能正確地接收該DATA包，NHF就會向節點i再次重新發出RREQ請求(此時RREQ=2，節點i就可以判斷有中繼節點存在，否則，在第一次RREQ到期時，節點i就會向節點NHF重傳DATA包)，RFN的通信范圍內的距離比NHF更接近匯點的節點就形成躍進節點集合L，集合中的每個節點l根據公式(8)來計算自己的度量，根據公式(9)，可以獲得躍進節點LPF節點。然后節點l設置一個定時器，該定時器的值與ml［t］成反比，定時器最先結束的節點就發送ACK控制包到節點RFN，此時，節點NHF也會收到該 ACK控制信息包，節點NHF就會停止轉發處理該DATA包。此時，LPF就扮演節點i的角色，來轉發數據包給其下一跳節點。

在t時刻，最佳躍進節點LPF為:

MCRICQR算法偽代碼:

躍進節點LPF向中繼節點RFN發送ACK包，從而阻止節點NHF處的數據包轉發過程;節點LPF再扮演節點i的角色;

4 仿真結果和分析

通過仿真實驗對所提出的跨層設計方法進行算法性能評估，下面依次給出實驗環境、實驗設計、實驗結果以及分析。

4.1 實驗環境

OMNET++［5］是一種面向對象的模塊化離散事件驅動的開源仿真器。在OMNET++環境下使用C++和NED實現了該算法，實驗設備是一臺運行 Windows XP SP2，具有 P42.8G Hz的 CPU，512M DDR內存的PC。實驗中，假設100個傳感器節點均勻地部署在500 m×500 m的監測區域內，sink節點被部署在(0，0)位置，節點的傳輸半徑設為100 m。仿真過程中取權重系數a=b=c=1，表明能量和距離、信噪比以及剩余存儲空間在仿真過程中認為它們按照相同權重來考慮。

4.2 實驗設計與性能分析

為了使仿真結果比較具有可信性，實驗設計時仿真的相關參數與文獻［6］中一致。QoS routing［6］路由基于節點知道自己的地理位置，使用802.11CSMA協議。實驗中，能量節點的減少與文獻［6］中一致，即包接收和包發送的所消耗能量比為1.05∶1.4。數據包載荷的大小設為512 bytes，數據包在源節點的生成速率為 0.5、1、1.5、2 包/s。每個仿真運行500 s，在仿真期間，網絡不斷裂。在仿真開始，所有的節點能量為500單位。最后取平均值進行比較。

在圖1中，MCRICQR比QoS routing平均時延低的原因在于，前者基于尺度選出最適的節點來轉發數據包;當有中繼節點存在時，不需要上一跳節點直接重傳數據包。圖2中，由于MCRICQR在進行選擇轉發節點的時候，考慮了節點的能量效用均衡，以及節點負載均衡的原因，獲得較長的網絡生存時間。QoS routing方法中，沒有考慮中間結點緩沖區溢出問題，一旦數據發生溢出，會產生丟包，就會造成數據的重傳，以及額外的控制包傳送而消耗網絡能量。圖3中，當數據包的期限足夠長的時候，兩種方法的數據傳遞率都很高，當數據包的期限短的時候，兩者的數據傳輸率都發生急劇降低。MCRICQR比QoS routing下降得稍微慢些，其原因在于，前者在調度時，綜合考慮了信道情況、擁塞情況等因素，避免了不必要的等待和沖突。圖4中，MCRICQR和QoS routing在數據生成速率低的時候，平均吞吐量都很高。隨著數據生成率的增加，兩者的吞吐量也隨之降低。前者進行轉發數據時，轉發節點的選擇基于尺度，競爭成為轉發節點，處在最有利轉發數據的節點，才會競爭成功，因此，其數據傳輸成功的概率就高，從而提高了網絡的平均吞吐量。

圖1 不同QoS路由平均包延遲Fig.1 Average packet delay for different routing schemes

圖2 不同路由方法下網絡生命時間Fig.2 Network lifetime for different routing schemes

圖3 不同期限下包傳遞率Fig.3 Packet delivery ratio for different deadlines

圖4 不同包生成率下吞吐量Fig.4 Throughput for different packet generation rates

5 結語

基于尺度的協同中繼自主轉發跨層QoS路由算法(MCRICQR)應用在WSN中。節點根據自身所處的位置、剩余能量、信道狀況、中繼隊列通信流以及節點緩沖區使用情況，形成一個綜合的度量尺度，根據尺度值進行競爭成為NHF、RFN、LPF節點，自主轉發數據。仿真結果表明，MCRICQR方法能夠根據網絡狀態及時轉發數據，時延低，提高網絡可靠性，具有較強的魯棒性和自適應性;MCRICQR方法是基于尺度進行競爭自主轉發數據，可以對網絡進行負載均衡，提高網絡吞吐量，延長網絡壽命，保障了WSN的QoS需求。同時，MCRICQR方法不需要為保持網絡拓撲信息和實現復雜的路由發現算法而消耗計算資源，它不會招致任何端到端的路由維護過程的過度開銷，提高了能量效率。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y ，et al.A survey on sensor networks［J］.IEEE Comm，2002，40(8):102 －116.

［2］Laneman J N，Tse D N C，Wornell G W.Cooperative diversity in wireless networks:efficient protocols and outage behavior［J］.IEEE Trans Inform，2004，50(12):3062 －3080.

［3］Lin X，Shroff N B.The impact of imperfect scheduling on crosslayer congestion control in wireless networks［C］//IEEE INFOCOM，Miami，FL，USA，2005.

［4］David Tse，Pramod Viswanath.無線通信基礎［M］.李 鏘，周 進，等譯，北京:人民郵電出版社，2007.

［5］http://www.omnetpp.org.

［6］Mahapatra A，Anand K，Agrawal D P.QoS and energy aware routing for real－ time traffic in wireless sensor networks［J］.Computer Communications，2006，29:437 －445.

Cross-layer QoS routing algorithm of metric-based cooperative relay in WSNs

Xu Nan1，Sun Yamin1，Yu Jiming2，Wang Hua3

(1.School of Computer Science and Technology，Nanjing University of Science and Technology，Nanjing 210094，China;2.School of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310014，China;3.School of Computer Science and Technology，Shandong University，Jinan 250023，China)

We proposed a cross-layer QoS routing algorithm which is metric-based cooperative relay initiative forwarding(MCRICQR).Nodes form a metric according to energy，channel，congestion and distance to sink.The node with maximal metric forwards or relays or leapfrogs the data in term of it’s own states.Simulation results show that MCRICQR can prolong the lifetime of network and guarantee the required QoS.It also can transmit data in time and load balance which improve the reliability and energy efficiency and throughput of WSN(wireless sensor network).

quality of service;cross-layer design;cooperative relay;initiative forwarding;wireless sensor network

TP393

A

1009－1742(2011)03－0045－05

2009－09－20;

2010－12－20

國家自然科學基金資助項目(60773101)

孫亞民(1946—)，男，江蘇張家港市人，教授，博士生導師，主要研究方向為計算機網絡與通信;E－mail:sunym@mail.njust.edu.cn