無線Mesh網絡中跨層協作的路由策略

馬亞蕾+郝東來2

摘 要： 網絡編碼可以提高無線Mesh網絡的吞吐量，但是網絡編碼在無線Mesh網絡中實際應用獲得最大網絡利用率是需要解決的問題。提出一種多路徑策略，能夠通過將網絡編碼和TCP進行最大化融合提高網絡的利用率。網絡編碼被加入到現有的網絡系統，通過解決速率控制問題和分組調度問題，調整源節點的數據編碼分塊，降低數據包重傳的次數，提高網絡的吞吐量。

關鍵詞： 無線Mesh網； 網絡編碼； 分組調度； 跨層協作

中圖分類號： TN913?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2014）18?0038?03

A routing strategy of cross?layer cooperation in wireless Mesh networks

MA Ya?lei 1， HAO Dong?lai 2

（1. Department of Computer Science， Shaanxi Vocational Technical College， Xian 710100， China；

2. Department of Information Transmission， Xian Communication Institute， Xian 710106， China）

Abstract： Network coding can increase the throughput of wireless Mesh networks， but to obtain the maximum utilization of the network in the practical application of network coding in wireless Mesh networks is the problem which needs to be solved. A multi?path routing strategy is proposed in this paper. It can improve network utilization by maximization fusion of the network coding and TCP. As the network coding was added to the existing network system， the number of data packet retransmission was reduced and the network throughput was increased by realizing rate control and packet scheduling， and adjustment data coding block of the source node block.

Keywords： wireless Mesh network； network coding； packet scheduling； cross?layer cooperation

近來，人們多采用基于IEEE 802.16 標準部署多天線的Mesh路由。這些天線在垂直信道工作，互相之間的干擾大大減少。在轉發之前，Mesh節點可以組合盡可能多的數據包，只要所有目的節點有足夠的信息可以提取出發送給各自的信息，并通過廣播進行發送[1?4]，但實際吞吐量增益并不高。首先NC（Network Coding）的行為和TCP的擁塞控制機制不能兼容，吞吐量增益比TCP流低很多[5?7]。其次，可獲得的增益依賴于網絡拓撲結構，包丟失和通信模式。現有的NC只過多考慮提高吞吐量，沒有考慮WMNs的延遲。

為解決以上問題，提出一種多徑路由策略叫做TCP?I2NC。通過把網絡編碼融合到TCP協議中解決易損耗的多天線多信道無線Mesh網絡中的隨機包丟失問題。本文將網絡編碼和TCP進行融合，TCP應用在Mesh客戶端或者網絡節點是透明的，并且與TCP的擁塞控制機制是兼容的。它建立在NUM框架上。每個TCP流的速率是在網絡實用規劃的基礎上自適應變化的。

1 相關工作

1.1 網絡編碼在無線Mesh網絡當中的應用

COPE通過異或組合多個數據包為一個來提高網絡的吞吐量[5]。TCP/NC首次將網絡編碼融合到TCP協議中，基于RANK矩陣。

1.2 NUM編碼系統

在網絡編碼內流，NCAQM機制被提出來NUM規劃來完全開發網絡編碼的機會[8]。Sudipta提出一個多路徑和編碼感知的COPE路由，基于一個理論構想來最大化吞吐量[9]。

2 系統模型說明

2.1 系統模型

數據包的轉換可以被模型為一個圖（N，L），N是節點集，L是無線鏈路集。R是Mesh節點上的天線集合，H是每個天線的可用垂直信道集合。Link（i，j）屬于L有能力Cij，傳輸延遲dij，丟包率pij。在鏈路上轉發的包要么被接收者收到，要么丟失。

2.2 標記

本文引入隨機線性網絡編碼的思想。系統中的節點可以進行網絡編碼。例如，假設節點A想發送數據包給節點B，A擁有數據包m1和m2，節點A從足夠大的伽羅華域選擇系數，轉發這兩個數據包的結合，q是域的大小，q在系統中被設置為256。

發送[n1=αm1+βm2]和[n2=λm1+μm2]，其中[α，β，λ∈GF（q）]。編碼過程則表示為：

[n1n2=αβλμm1m2=Cm1m2]

TCP流：F是從源節點到目的節點TCP流的集合。每一個流f屬于F可以成功到達目的地。每一個流f屬于F都和速率Xf以及功能函數U（xf）（嚴格凹函數）有關系。不同的平衡可以通過不同的功能函數達到。一類功能函數被定義為：

[Ua（x）=logx， a=1x1-a1-a， a≥0，a≠1] （1）

功能函數在該系統中的定義為：

[U（x）=Ua=1（x）=-1x] （2）

路由：網絡可用最大化規劃。

一個網絡是穩定的，如果節點i的整個輸出交通比整體的輸入大，

[rfij-rfij-xf{s（f）=i}≥0] （3）

若[s（f）=i]，則[xf{s（f）=i}=xf]，否則該值為0，同時：

[rfij≥0] （4）

[f∈Frfij≤cij] （5）

網絡利用的總和為[f∈Fu（xf）]。網絡利用率的最大化公式是尋找解決最大化[f∈Fu（xf）]所對應的式（3）～式（5）。

3 協議實施過程

該方案將網絡編碼融入到TCP當中，可以有效降低隨機丟失并且顯著提高TCP 的吞吐量。通過一個單跳的流內和流間網絡編碼機制，解決NUM問題分解出來的速率控制和包調度算法被提出來解決擁塞控制。如圖1所示，一個新的網絡編碼層被引入。在無線Mesh網絡當中的無線節點。在每一個NC層，有一個發送者模型和接收者模型。

圖1 協議棧中新的網絡編碼層

他們主要負責分別發送和接收數據包，基于同一路TCP流。一個Mesh 節點用隊列Qel來緩沖那些TCP數據包（需要被轉發到目的地）。如果一個節點是終節點，他用編碼隊列Qe0來緩沖TCP數據包（那些在他的TCP流里或網絡側節點沒有被TCP流確認）。Pel是鏈路1的丟包率。

算法描述：

鏈路1發送模塊的1（i，j）：

（1） Sf=0

如果節點i是數據流f的源信息節點，計算[Xf=argmaxU（xf）-xfqf]；

Sf +=[xf10]；

生成Sf向下取整應答給傳輸層；

[Sf-=Sf]。

（2） 從隊列Qel挑出N1個數據包，轉發[N1（1-Pel）]線性結合，保存發送包的數目。

（3） 如果超時，則生成NACK給編碼器。

（4） 檢查是否有新的TCP隊列包，若有則按順序發送。

鏈路1的接收模塊1（i，j），若收到數據包a：

（1） 如果a是一個TCP連接的控制數據包，直接轉發；

（2） 如果a是一個二進制TCP數據包，則尋找a的下一個鏈路m，插入到Qem；

（3） 如果a是一個編碼數據包，緩沖，解碼。讓m表示它的下一鏈路：

① 如果解碼成功，生成ACK發送給發送者

② 否則，啟動接收計時器。

（4） 如果a是NACK，讓r表示解碼系數矩陣的階：

① 如果r=N1，刪除緩沖的TCP數據包，重新計算Pel，qif，釋放編碼器；

② 否則生成[N1（1-Pel）-r]個TCP數據包的對應編碼塊的隨機組合。

4 結 語

本文提出一種多路徑策略，能夠通過將網絡編碼和TCP進行最大化融合提高網絡的利用率。網絡編碼被加入到現有的網絡系統，通過解決速率控制問題和分組調度問題，調整源節點的數據編碼分塊，降低數據包重傳的次數，提高網絡的吞吐量。

參考文獻

[1] AKYILDIZ I， WANG Xu?dong， WANG Wei?lin. Wireless Mesh networks： a survey [J]. Computer Networks， 2005， 47（4）： 445?487.

[2] RAMACHANDRAN K， BELDING E， ALMEROTH K， et al. Interference?aware channel assignment in multi?radio wireless Mesh networks [C]// Proceedings of INFO?COM. Barcelona，Catalunya， Spain： IEEE Computer Society， 2006： 1?12.

[3] GUPTA P， KUMAR P， Capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46： 388?404.

[4] AKHTAR N， MOESSNER K. On the nominal capacity of multi?radio multi?channel wireless Mesh networks [J]. Computer Communications， 2008， 31（8）： 1475?1483.

[5] KATTI S， RAHUL H， HU Wen?jun， et al. XORs in the air： practical wireless network coding [J]. IEEE / ACM Transactions on Networking， 2008， 16（3）： 497?510.

[6] HUANG Yong， GHADERI M， TOWSLEY D， et al. TCP performance in coded wireless Mesh networks [C]// Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks. San Francisco， USA： IEEE Computer Society， 2008： 179?187.

[7] HASSAYOUN S， MAILL P. On the impact of random losses on TCP performance in coded wireless Mesh networks [C]// Proceedings of the 29th Conference on Information Communications. San Diego， CA， USA： IEEE Computer Society， 2010： 1?9.

[8] SEFEROGLU H， MARKOPOULOU A. Network coding?aware queue management for unicast flows over coded wireless networks [C]// Proceedings of IEEE NetCod. Toronto， Canada： IEEE Computer Society， 2010： 1?6.

[9] SENGUPTA S， RAYANCHU S， BANARJEE S. An analysis of wireless network coding for unicast sessions：the case for coding?aware routing [C]// Proceedings of the 26th IEEE International Conference on Computer Communications. Anchorage， Alaska， USA： IEEE Computer Society， 2007： 1028?1036.

[Ua（x）=logx， a=1x1-a1-a， a≥0，a≠1] （1）

功能函數在該系統中的定義為：

[U（x）=Ua=1（x）=-1x] （2）

路由：網絡可用最大化規劃。

一個網絡是穩定的，如果節點i的整個輸出交通比整體的輸入大，

[rfij-rfij-xf{s（f）=i}≥0] （3）

若[s（f）=i]，則[xf{s（f）=i}=xf]，否則該值為0，同時：

[rfij≥0] （4）

[f∈Frfij≤cij] （5）

網絡利用的總和為[f∈Fu（xf）]。網絡利用率的最大化公式是尋找解決最大化[f∈Fu（xf）]所對應的式（3）～式（5）。

3 協議實施過程

該方案將網絡編碼融入到TCP當中，可以有效降低隨機丟失并且顯著提高TCP 的吞吐量。通過一個單跳的流內和流間網絡編碼機制，解決NUM問題分解出來的速率控制和包調度算法被提出來解決擁塞控制。如圖1所示，一個新的網絡編碼層被引入。在無線Mesh網絡當中的無線節點。在每一個NC層，有一個發送者模型和接收者模型。

圖1 協議棧中新的網絡編碼層

他們主要負責分別發送和接收數據包，基于同一路TCP流。一個Mesh 節點用隊列Qel來緩沖那些TCP數據包（需要被轉發到目的地）。如果一個節點是終節點，他用編碼隊列Qe0來緩沖TCP數據包（那些在他的TCP流里或網絡側節點沒有被TCP流確認）。Pel是鏈路1的丟包率。

算法描述：

鏈路1發送模塊的1（i，j）：

（1） Sf=0

如果節點i是數據流f的源信息節點，計算[Xf=argmaxU（xf）-xfqf]；

Sf +=[xf10]；

生成Sf向下取整應答給傳輸層；

[Sf-=Sf]。

（2） 從隊列Qel挑出N1個數據包，轉發[N1（1-Pel）]線性結合，保存發送包的數目。

（3） 如果超時，則生成NACK給編碼器。

（4） 檢查是否有新的TCP隊列包，若有則按順序發送。

鏈路1的接收模塊1（i，j），若收到數據包a：

（1） 如果a是一個TCP連接的控制數據包，直接轉發；

（2） 如果a是一個二進制TCP數據包，則尋找a的下一個鏈路m，插入到Qem；

（3） 如果a是一個編碼數據包，緩沖，解碼。讓m表示它的下一鏈路：

① 如果解碼成功，生成ACK發送給發送者

② 否則，啟動接收計時器。

（4） 如果a是NACK，讓r表示解碼系數矩陣的階：

① 如果r=N1，刪除緩沖的TCP數據包，重新計算Pel，qif，釋放編碼器；

② 否則生成[N1（1-Pel）-r]個TCP數據包的對應編碼塊的隨機組合。

4 結 語

本文提出一種多路徑策略，能夠通過將網絡編碼和TCP進行最大化融合提高網絡的利用率。網絡編碼被加入到現有的網絡系統，通過解決速率控制問題和分組調度問題，調整源節點的數據編碼分塊，降低數據包重傳的次數，提高網絡的吞吐量。

參考文獻

[1] AKYILDIZ I， WANG Xu?dong， WANG Wei?lin. Wireless Mesh networks： a survey [J]. Computer Networks， 2005， 47（4）： 445?487.

[2] RAMACHANDRAN K， BELDING E， ALMEROTH K， et al. Interference?aware channel assignment in multi?radio wireless Mesh networks [C]// Proceedings of INFO?COM. Barcelona，Catalunya， Spain： IEEE Computer Society， 2006： 1?12.

[3] GUPTA P， KUMAR P， Capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46： 388?404.

[4] AKHTAR N， MOESSNER K. On the nominal capacity of multi?radio multi?channel wireless Mesh networks [J]. Computer Communications， 2008， 31（8）： 1475?1483.

[5] KATTI S， RAHUL H， HU Wen?jun， et al. XORs in the air： practical wireless network coding [J]. IEEE / ACM Transactions on Networking， 2008， 16（3）： 497?510.

[6] HUANG Yong， GHADERI M， TOWSLEY D， et al. TCP performance in coded wireless Mesh networks [C]// Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks. San Francisco， USA： IEEE Computer Society， 2008： 179?187.

[7] HASSAYOUN S， MAILL P. On the impact of random losses on TCP performance in coded wireless Mesh networks [C]// Proceedings of the 29th Conference on Information Communications. San Diego， CA， USA： IEEE Computer Society， 2010： 1?9.

[8] SEFEROGLU H， MARKOPOULOU A. Network coding?aware queue management for unicast flows over coded wireless networks [C]// Proceedings of IEEE NetCod. Toronto， Canada： IEEE Computer Society， 2010： 1?6.

[9] SENGUPTA S， RAYANCHU S， BANARJEE S. An analysis of wireless network coding for unicast sessions：the case for coding?aware routing [C]// Proceedings of the 26th IEEE International Conference on Computer Communications. Anchorage， Alaska， USA： IEEE Computer Society， 2007： 1028?1036.

[Ua（x）=logx， a=1x1-a1-a， a≥0，a≠1] （1）

功能函數在該系統中的定義為：

[U（x）=Ua=1（x）=-1x] （2）

路由：網絡可用最大化規劃。

一個網絡是穩定的，如果節點i的整個輸出交通比整體的輸入大，

[rfij-rfij-xf{s（f）=i}≥0] （3）

若[s（f）=i]，則[xf{s（f）=i}=xf]，否則該值為0，同時：

[rfij≥0] （4）

[f∈Frfij≤cij] （5）

網絡利用的總和為[f∈Fu（xf）]。網絡利用率的最大化公式是尋找解決最大化[f∈Fu（xf）]所對應的式（3）～式（5）。

3 協議實施過程

該方案將網絡編碼融入到TCP當中，可以有效降低隨機丟失并且顯著提高TCP 的吞吐量。通過一個單跳的流內和流間網絡編碼機制，解決NUM問題分解出來的速率控制和包調度算法被提出來解決擁塞控制。如圖1所示，一個新的網絡編碼層被引入。在無線Mesh網絡當中的無線節點。在每一個NC層，有一個發送者模型和接收者模型。

圖1 協議棧中新的網絡編碼層

他們主要負責分別發送和接收數據包，基于同一路TCP流。一個Mesh 節點用隊列Qel來緩沖那些TCP數據包（需要被轉發到目的地）。如果一個節點是終節點，他用編碼隊列Qe0來緩沖TCP數據包（那些在他的TCP流里或網絡側節點沒有被TCP流確認）。Pel是鏈路1的丟包率。

算法描述：

鏈路1發送模塊的1（i，j）：

（1） Sf=0

如果節點i是數據流f的源信息節點，計算[Xf=argmaxU（xf）-xfqf]；

Sf +=[xf10]；

生成Sf向下取整應答給傳輸層；

[Sf-=Sf]。

（2） 從隊列Qel挑出N1個數據包，轉發[N1（1-Pel）]線性結合，保存發送包的數目。

（3） 如果超時，則生成NACK給編碼器。

（4） 檢查是否有新的TCP隊列包，若有則按順序發送。

鏈路1的接收模塊1（i，j），若收到數據包a：

（1） 如果a是一個TCP連接的控制數據包，直接轉發；

（2） 如果a是一個二進制TCP數據包，則尋找a的下一個鏈路m，插入到Qem；

（3） 如果a是一個編碼數據包，緩沖，解碼。讓m表示它的下一鏈路：

① 如果解碼成功，生成ACK發送給發送者

② 否則，啟動接收計時器。

（4） 如果a是NACK，讓r表示解碼系數矩陣的階：

① 如果r=N1，刪除緩沖的TCP數據包，重新計算Pel，qif，釋放編碼器；

② 否則生成[N1（1-Pel）-r]個TCP數據包的對應編碼塊的隨機組合。

4 結 語

本文提出一種多路徑策略，能夠通過將網絡編碼和TCP進行最大化融合提高網絡的利用率。網絡編碼被加入到現有的網絡系統，通過解決速率控制問題和分組調度問題，調整源節點的數據編碼分塊，降低數據包重傳的次數，提高網絡的吞吐量。

參考文獻

[1] AKYILDIZ I， WANG Xu?dong， WANG Wei?lin. Wireless Mesh networks： a survey [J]. Computer Networks， 2005， 47（4）： 445?487.

[2] RAMACHANDRAN K， BELDING E， ALMEROTH K， et al. Interference?aware channel assignment in multi?radio wireless Mesh networks [C]// Proceedings of INFO?COM. Barcelona，Catalunya， Spain： IEEE Computer Society， 2006： 1?12.

[3] GUPTA P， KUMAR P， Capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46： 388?404.

[4] AKHTAR N， MOESSNER K. On the nominal capacity of multi?radio multi?channel wireless Mesh networks [J]. Computer Communications， 2008， 31（8）： 1475?1483.

[5] KATTI S， RAHUL H， HU Wen?jun， et al. XORs in the air： practical wireless network coding [J]. IEEE / ACM Transactions on Networking， 2008， 16（3）： 497?510.

[6] HUANG Yong， GHADERI M， TOWSLEY D， et al. TCP performance in coded wireless Mesh networks [C]// Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks. San Francisco， USA： IEEE Computer Society， 2008： 179?187.

[7] HASSAYOUN S， MAILL P. On the impact of random losses on TCP performance in coded wireless Mesh networks [C]// Proceedings of the 29th Conference on Information Communications. San Diego， CA， USA： IEEE Computer Society， 2010： 1?9.

[8] SEFEROGLU H， MARKOPOULOU A. Network coding?aware queue management for unicast flows over coded wireless networks [C]// Proceedings of IEEE NetCod. Toronto， Canada： IEEE Computer Society， 2010： 1?6.

[9] SENGUPTA S， RAYANCHU S， BANARJEE S. An analysis of wireless network coding for unicast sessions：the case for coding?aware routing [C]// Proceedings of the 26th IEEE International Conference on Computer Communications. Anchorage， Alaska， USA： IEEE Computer Society， 2007： 1028?1036.