在網狀網路下利用線性組合技術實現管線式的臨機路由

Abstract

臨機路由是近年來無線網路傳輸領域中的一項重要的探索方向，其可以增加在網狀網路中使用unicast情況時的效能。基本的臨機路由技術會使各個節點高頻率地接收到相同封包而造成網路的負擔，因此有研究提出利用排程的方法來避免收到相同的封包，但排程的方式亦存在過於浪費頻寬、以及需要大量的控制訊息之問題。利用線性組合的技術可以改進在排程中需要等待優先權較高的節點回傳訊息後才能傳送本身之封包的缺點，方法是將資料切成多個區段並對同一個區段中的封包進行線性組合，而其中該於何時傳送下一個區段及如何決定可幫忙傳送的節點則成為一個重要的議題。若每次必須等到目的地端收完某區段中的封包並回送acknowledgment給來源端後才能傳送新的區段的話，會造成效率的低落，若是在大範圍的網路底下，更會因為acknowledgement回送時間過長而使效率更差。為了增進傳送的效能，我們提出了名為PipelineOR的演算法來解決這個問題，主要的觀念在於當來源端傳送某段時間後，中介節點可能已經收滿足夠的封包可供解碼，此時中介節點便可以取代來源端傳送封包，藉此降低為了等待目的地端收滿全部的封包後來源端才能開始傳送下一段區塊所造成的延遲。另外因為重複的封包對於解碼並無幫助，演算法也會觀察在網路中是否有不需要用到的節點，藉由使優先 權較低的節點停止傳送來降低碰撞和互搶頻寬的機會。

Recently, Opportunistic Routing has been widely explored to improve the unicast performance in wireless mesh networks. A number of recent papers introduce opportunistic routing in wireless mesh networks by utilizing schedule in order to avoid receiving duplication packets in node. Unfortunately, all of them prevent spatial reuse and thus may underutilize the wireless medium because of the node must wait until higher priority node completes. With linear combination, opportunistic routing can be implemented without complex scheduler protocol. Linear combination partitions the stream into multiple segments and combines only packets in the same segment. It is significant to decide when the next segment can be sent. In previous studies the source can send next segment only when destination receives enough packets to decode and retransmit acknowledgement to source. In this paper, we propose PipelineOR, a new protocol that uses linear combination method and select necessary forwarding nodes to improve throughput. In our algorithm, if one node receives a packet from another forwarder it also can know all packets that have stored in upstream node instead of just one re-combining packet and corresponding decoding coefficiences. In linear combination, we can only check the coefficient to determine whether forwarding nodes have enough packets to decode. If yes, send an acknowledgement to the sender. When the sender receives this acknowledgement it can send next segment packet as soon. We also check the dependency for each node and prune unnecessary node to avoid collision. Experimental results show that PepelineOR's throughput is 15%-20% higher than CodeOR.