用于VSN的低延時多徑路由

吳 迪， 尹首一， 李國林

（清華大學微電子所，北京100084）

0 引言

無線傳感器網絡（WSN）用于感知和測量物理世界，實現了人與物理世界之間的溝通。隨著技術的進步簡單的物理量的測量已不能滿足人們的需求。視頻傳感器網絡(VSN)作為一種新興的傳感器網絡已越來越受到人們的關注，其最突出的特點就是對網絡的實時性有很高的要求而且需要更高的數據傳輸帶寬。無線傳感器網絡路由協議分為兩類，一類是平面路由，另一類是層次化路由。前者如 SPIN[1]、EAR[2]，后者代表是LEACH[3]。這些協議均不是從減小網絡延時的角度出發的，本文提出并實現了一種新的基于多徑路由的算法，MPTT(Multi-path Predicted Transmission Time)這種算法不僅能夠降低數據的傳輸延時，而且相對于單徑路由DSR可以提供更高的網絡帶寬，更適合視頻傳感器網絡的要求。

1 MPTT算法

1.1 MPTT 的單路徑延時

MPTT是基于文獻[4]的思想，首先通過從MAC層建模根據節點以及其鄰居節點的流量信息計算出每條鏈路的延時，然后比較分析所得到的每條路徑的延時并進行流量分配，使總體的數據流延時達到最小。根據文獻[4]一跳的傳輸延時可以表示為：

其中Ts表示數據包發送需要的時間，其值與路徑上鄰居節點的流量信息有關，Tq表示數據等待發送需要的時間，λij表示這條鏈路上傳輸的數據流量。如果一條路徑上需要n跳的轉發，那么總體的延時PD(Path Delay)可以表示為：

Tn表示第n跳的延時。總體上可以得出，路徑延時既與發送路徑鄰居節點的流量信息相關又與自身數據流量大小相關，流量越大路徑的延時也就越大。

1.2 MPTT多徑流量分配

現在我們通過改進的 DSR[5]算法得到了m條路徑。假設要在這些路徑上分配流量Ftotal，分配給每條路徑上的流量分別為F1,F2,…,Fm則有：

路徑的延時與這條路徑上的數據流量有關，路徑上的數據流量越大則這條路徑的延時就越大。為了得到數據流的最小延時，應該首先將流量分配給延時最小的路徑，隨著分配流量的加大路徑的延時也相應的增加。當其延時大到該路延時已不再是所有路徑中延時最小的路徑時，就重新尋找延時最小的路徑并將剩余流量分配給新尋找出來的路徑。如此循環下去直到分配完所有的流量為止。因此最終的結果就是所有被使用的路徑其延時相同。如果使用了k條路徑則分配給每條路徑的流量應該滿足如下的方程組：

可以利用循環迭代的方式求出其近似解。這樣就求出了延時最小的流量分配方案。

2 MPTT的實現

整個的路由算法可以由圖1來實現。目前路由發現的算法的代表是DSR和AODV[6]。MPTT的路由發現的過程是基于DSR協議，在此基礎上還完成了路徑流量信息的采集。首先每個節點根據自身發送和接收數據包情況來建立本地流量信息表。當某一個節點想要發送數據時就發起一個路由請求，路由請求是通過全網廣播的方式發送出去的，發送路由請求的同時也將本地的流量信息搭載在數據之后。當其鄰居節點收到路由申請之后一方面記錄搭載在路由申請之后的流量信息到鄰居鏈路信息表中，另一方面如果檢測到本地節點為目標地址則發出路由回復，否則將本地的流量信息表搭載在數據之后繼續廣播。當路由申請節點收到路由回復之后就開始檢測這條路徑，如果該路徑為收到的第一條路由回復，則將其記錄在本地的路由信息表之中。如果不是第一條路由回復，則用已有的路由檢測新得到的路由，如此逐步的檢測所有新得到的路徑。這樣就可以得到多條互不相關的路徑。然后開始采集各個路徑的流量信息，在采集之后就利用前面所提出的路由算法進行流量分配，開始發送數據，到此為止完成了發送數據的整個過程。

圖1 MPTT實現的框架圖

3 仿真結果及分析

3.1 仿真過程

本文所采用的就是基于TinyOS的仿真平臺TOSSIM。仿真的網絡為由 10個節點組成的具有三條互不相關路徑的網絡，三條路徑的跳數分別為 3、4、4。網絡的數據傳輸帶寬為 40 Kb/s。仿真的過程是從源節點以遞增的速率向目的節點發送100個數據包，速率從1～20 Kb/s，間隔為1 Kb/s。從數據包的平均延時和丟包數量來檢測兩個方面比較 MPPT和單路徑路由DSR協議。

3.2 仿真結果

從圖 2中我們可以看出在分配的數據流量比較小的時候MPTT與DSR路由的延時基本一致有時還比其小。這是由于在低速率時流量基本上分配給了跳數最少的路徑，但是由于DSR每次所選出的路徑具有隨機性并不是每次都能選出最短的路徑來傳輸數據，所以有時其延時比較大。MPTT總是選擇跳數最少的路徑來發送數據。除此之外圖2中的虛線還表示出了單徑所能分配的極限流量。在到達極限傳輸流量之后DSR無法正常工作，然而MPTT卻依然可以發送數據，提供了更高的數據流帶寬。

圖2 MPTT與DSR延時比較

圖3 MPTT與DSR丟包率比較

上頁圖3顯示出了在傳輸相同的數據流時，MPTT可以提供更低的丟包率。這是由于當某一路上的數據流量增大的時候，該路上的數據包碰撞概率會以指數形式增加，當把流量分配給多條路徑時就減小了數據包碰撞的概率進而減小了丟包率。

4 結語

MPTT是通過從MAC層建模，根據路徑上每個節點的鄰居流量信息計算出來每條鏈路的延時，再根據延時情況進行流量分配。利用 MPTT所得到的總體延時在流量不大的情況下與單徑路由所選擇的延時最小的路徑相當。隨著所分配流量的加大，MPTT的延時比DSR要小，而且可以提供DSR所不能提供的高速據帶寬。另一方面 MPTT可以降低丟包率，提高數據流傳輸的可靠性。因此 MPTT是一種更適合視頻數據流服務的路由協議。

[1] Xu Ning, Rangwala Sumit, Chintalapudi Krishna Kant, et al. A Wireless Sensor Network for Structural Monitoring[C].Baltimore: Association for Computing Machinery, 2004: 13-24.

[2] Mann Raminder P, Namuduri Kamesh R, Pendse Ravi. Energyaware Routing Protocol for Ad Hoc Wireless Sensor Networks[J].Eurasip Journal on Wireless Communications and Networking,2005(05):635-644.

[3] Heinzelman Wendi B, Chandrakasan Anantha P, Balakrishnan Hari. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(04): 660-670.

[4] Yin Shouyi, Xiong Yongqiang, Zhang Qian, et al. Trafficaware Routing for Real-time Communications in Wireless Multi-hop Networks[J]. Wireless Communications and Mobile Computing, 2006,6(06):825-843.

[5] Johnson D, Maltz D, HuYih-Chun. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)[EB/OL].(1999-10-01)[2009-03-11] http://www.ietf.org/rfc/rfc4728.txt.2007.

[6] Perkins C E, Royer E M, Das S R, et al. Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks[J].IEEE Personal Communications, 2001,8(01):16-28.