隨著無線運算技術的進步，行動隨意式網路（mobile ad hoc network, MANET）快速地成長，相關的研究也逐漸受到各界重視。MANET係由行動平台或節點所組成；邏輯上，每一個節點都是擁有多個主機接連的路由器與無線通訊設備，節點都可以自由地任意行動，沒有基地台（base station）等固定之基礎設施（infrastructure），是一個具有分散式（distributed）、多重跳躍（multi-hop）特性的無線行動網路。近年來許多研究主要著重在無線網路動態路徑搜尋方式的發展，以便有效地建立兩節點之間的通訊路徑。著名的路由協定相繼被提出，例如：動態目標序列距離向量路由協定（Dynamic Destination Sequenced Distance Vector, DSDV），動態來源端路由協定（Dynamic Source Routing, DSR），隨意隨選距離向量路由協定（Ad Hoc On Demand Distance Vector, AODV），臨時排序路由演算法（Temporally Ordered Routing Algorithm, TORA）和區域路由演算法（Zone Routing Protocol, ZRP）等論述。
在本論文中，首先介紹兩個與研究相關的MANET網路協定。在多點跳躍（multi-hop）隨意式（ad hoc）無線網路環境中，AODV是網路層中動態搜尋路徑時常採用的路由協定，它是以最少的跳躍節點作為路徑選擇的依據；相對地，IEEE 802.11 DCF則是資料鏈結層中最常被採用的媒介存取控制策略。在隨意式（ad hoc）無線網路中為了順利傳遞資料封包，網路層的協定與資料鏈結層的機制必須協同運作，上層的協定（AODV）使用下層的媒介存取控制機制，下層的協定（IEEE 802.11 DCF）服務上層所傳送下來的資料封包，上、下相鄰兩層通訊協定息息相關、互相交聯，共同競爭和分享無線網路資源。然而，在多重跳躍（multi-hop）隨意式（ad hoc）無線環境中，由於各節點共用無線傳輸媒介，使用者（節點）競爭並共享無線傳輸通道的頻寬，每一個節點之吞吐量（throughput）不僅僅受到通道本身容量的限制，而且亦和鄰近節點的通道使用狀況息息相關。每一節點在傳輸封包時，都會與上游（upstream）和下游（downstream）節點爭相使用共享的無線通道資源，此一效應將導致資料傳輸過程中，部份節點之封包壅塞或遺失，進而嚴重地影響隨意式（ad hoc）無線網路的傳輸效能。因此，無線行動隨意式網路的另一重要議題－提升網路資料傳輸效能（data transmission efficiency），將是本論文探討的重點。如何控制此共享媒介的存取品質，協調有限的無線頻道資源，有效地維持兩節點之間的通訊路由，將是一個重要而複雜的課題。
接下來，我們探討多重跳躍（multi-hop）隨意式（ad hoc）無線網路運作時，可能會遇到的一些資料傳輸問題：包括了隱藏節點問題（hidden terminal problem）、暴露節點問題（exposed terminal problem）、接收節點阻隔現象（receiver blocking problem）、資料流內部封包競爭（intra-flow contention）及資料流外部封包競爭（inter-flow contention）等。這些問題可能導致網路層AODV路由協定封包傳輸效能不佳；然而，上述資料傳輸問題主要導因於資料鏈結層的訊框碰撞與傳輸干擾。許多文獻顯示，IEEE 802.11標準僅適用於單點跳躍的無線區域網路：IEEE 802.11標準是資料鏈結層的協定，採用多重存取/碰撞避免（Carrier Sense Multiple Access / Collision Avoidance, CSMA/CA）的傳輸策略，負責媒介存取控制及無線通道的分派，IEEE 802.11 DCF標準定義了兩種媒介存取控制機制— basic access及RTS/CTS，分別採用雙向（data/ack）交握（two-way handshaking）及4向（RTS/CTS/data/ack）交握（four-way handshaking）的溝通方式。IEEE 802.11 MAC標準雖已被成功地應用於一般單點跳躍的無線區域網路，作為媒介存取控制的傳輸策略；然而，在多點跳躍（multi-hop）隨意式（ad hoc）無線網路環境下，因為相鄰節點必須共用及分享無線傳輸媒介，訊框碰撞與傳輸干擾的機率將遠大於單點跳躍的無線區域網路，導致路徑中某些節點的壅塞，各中間節點持續累積過多的資料封包，使競爭加劇，終因介面佇列（interface queue）空間不足而丟棄封包。這些發生在資料鏈結層的訊框碰撞與傳輸干擾，更進一步地將影響上一層（IP layer）的網路傳輸效能及路由維護機制。
本論文針對隨意式（ad hoc）無線網路之主動式路由、多點跳躍的特性及媒介存取控制機制所引發的問題，以網路層AODV協定及資料鏈結層 IEEE 802.11標準作為研究標的。提出一種跨越網路層（IP layer）及資料鏈結層（MAC layer）的路由架構—順序優先排程之AODV協定（AODV Protocol with Scheduling Priority Contention Window in MAC Layer, AODV-SCW）；將上層AODV路由協定之資料傳輸路徑總長，及距離目的地節點剩餘跳躍數當作耦合參數，傳遞給下層 IEEE 802.11協定，做為後續各節點競爭視窗大小的計算依據，指派較高的通道擷取機率給下游（downstream）節點，達到較佳的封包排程效果。此一架構打破傳統協定上、下層間各自獨立的運作模式，彼此互相分享網路狀態資訊，可以減少下層 IEEE 802.11協定在傳送過程中，引發的封包碰撞及資料遺失，間接地改善上層AODV協定的網路傳輸效能。最後，根據我們所做的模擬實驗結果，分別與傳統的basic access及RTS/CTS機制作比較並分析結果，驗證我們所提出的方法（AODV-SCW），在共用無線傳輸媒介的隨意式（ad hoc）網路中，可以提升端對端吞吐量（end to end throughput）、改善封包成功送達率（packet delivery ratio）、減少封包路由成本（normalized routing load）及降低鏈路失敗機率（probability of link failure）。基於上述結論，當我們探討MANET網路協定設計及性能改善時，務必將資料鏈結層的傳輸標準和網路層的路由協定同時列入、整體考量，才能徹底解決無線網路所遭遇的問題，提升網路傳輸效能。

Recent advancements in wireless technologies and mankind’s long-time dream of free communication are the driving forces behind the proliferation of wireless local area networks and the “hot” research activities in mobile ad hoc networks. One of the most active topics is the medium access control protocol, which coordinates the efficient use of the limited shared wireless resource. However, in these wireless networks, the limited wireless spectrum, time-varying propagation characteristics, distributed multiple access control, and low complexity constraints together impose significant challenges for the MAC protocol design to provide reliable wireless communications with high data rates.
Among all MAC protocols, random medium access control protocols have been widely studied for wireless networks due to their low cost and easy implementation. The IEEE 802.11 MAC is such a protocol that has been successfully deployed in wireless local area networks and has also been incorporated in many wireless multi-hop mobile ad hoc networks. It uses two way (i.e., DATA/ACK) or four way (i.e., RTS/CTS/DATA/ACK) handshake procedures. The RTS and CTS procedures are used to avoid collisions with long data packets. The value of the NAV (network allocation vector) carried by RTS or CTS is used to reserve the medium to avoid potential collisions (i.e., virtual carrier sensing) and thus mitigates the hidden terminal problem. The ACK is used to confirm successful transmission without errors. However, there are still many problems that the IEEE 802.11 MAC has not adequately addressed. The hidden terminals may introduce collisions and the exposed terminals may lead to low throughput efficiency, the receiver blocking problem (i.e., the intended receiver does not respond to the sender with CTS or ACK due to the interference or virtual carrier sensing operational requirements for the other ongoing transmissions) hence deserves serious consideration. The intra-flow and inter-flow contentions may bring server interferences and collisions in traffic flows. In fact, these problems become more severe in multi-hop ad hoc environment. Not only greatly decreases the end-to-end throughput, but also increases the end-to-end delay; starves some traffic flows or nodes, and causes unnecessary re-routing procedures.
Moreover, higher layer network protocols may be affected by the wireless MAC protocols. It has been shown in many articles that multi-hop ad hoc networks perform poorly with TCP traffic and heavy UDP traffic. Because all wireless links in the neighborhood share the same wireless resources. All traffic flows passing through these links need to contend for the channel before transmission. Hence, severe MAC layer interferences and collisions can result in the contentions among traffic flows. On the other hand, MAC contentions can introduce network congestion with backlogged packets, which implies that network congestion is closely coupled with MAC contentions. In this dissertation, we present a framework of multi-hop packet scheduling to achieve high throughput, good packet delivery ratio, low routing load, and small link failure probability for traffic flows in the shared channel environment. The routing information about the total hop count and the remaining hop count, required by a packet to reach its destination, is exploited by the MAC layer in order to recalculate the contention window size of nodes along the routing path and to give the priorities for the packets that are closer to their destination. Extensive simulations show that the proposed scheme is able to earn significant improvement over conventional algorithm.

[1] S. Motegi, K. Yoshihara, and H. Horiuchi, “Service discovery for wireless ad hoc networks”, Wireless Personal Multimedia Communications, The 5th International Symposium on, Volume 1, pp. 232 – 236 (2002).
[2] F. Alizadeh-Shabdiz and S. Subramaniam, “Analytical models for single-hop and multi-hop ad hoc networks”, Broadband Networks, BroadNets Proceedings. First International Conference, pp. 449 – 458 (2004).
[3] A. Vasiliou and A. A. Economides, “MANETs for environmental monitoring”, Telecommunications Symposium, International Conference, pp. 813 – 818 (2006).
[4] R. A. Rashid, S. Arifin, M. Rahim, M. A. Sarijari, and N. H. Mahalin, “Home healthcare via wireless biomedical sensor network”, RF and Microwave Conference, RFM 2008 IEEE International, pp. 511 – 514 (2008).
[5] B. S. Manoj and C. Murthy, “Ad Hoc Wireless networks: Issues and Challenges”, Technical report, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India (2003).
[6] C. Rosenberg, “Challenges in multi-hop networks”, Next Generation Internet Design and Engineering, NGI '06. 2006 2nd Conference (2006).
[7] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers”, Proceedings of the SIGCOMM ’94, pp. 234 – 244 (1994).
[8] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks, in Mobile Computing”, T. Imielinski and H. Korth, Eds. Kluwer. Academic Publishers, pp. 153 – 181 (1996).
[9] C. E. Perkins and E. M. Royer, “Ad-Hoc On-Demand Distance Vector Routing”, in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, L.A., pp. 90 – 100 (1999).
[10] V. D. Park and M. S. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks”, INFOCOM’97, pp. 1405 – 1413 (1997).
[11] M. R. Pearlman and Z. J. Haas, “Determining the Optimal Configuration for the Zone Routing Protocol”, IEEE JSAC, pp. 1395 – 1414 (1999).
[12] J. Li, C. Blake, D. Couto, H. Lee, and R. Morris, “Capacity of Ad Hoc Wireless Network”, in Proceedings of ACM MobiCom (2001).
[13] S. Xu and T. Safadawi, “Does the IEEE 802.11 MAC Protocol Work Well in Multi-hop Wireless Ad Hoc Networks? ”, IEEE Comm. Magazine, vol. 39, pp 130 – 137 (2001).
[14] T. G. Basavaraju, S. K. Sarkar, and C. Puttamadappa, “Impact of MAC Layer on the Performance of Routing Protocols in Mobile Ad hoc Networks”, International Journal of Information Technology, vol. 3, no. 4, pp. 237 – 244 (2006).
[15] Jae-Yong Yoo and Jong-Won Kim, “Maximum End-to-End Throughput of Chain-Topology Wireless Multi-Hop Networks”, Wireless Communications and Networking Conference, WCNC 2007. IEEE, pp. 4279 – 4283 (2007).
[16] Ping Chung Ng and Soung Chang Liew, “Throughput Analysis of IEEE802.11 Multi-Hop Ad Hoc Networks”. Networking, IEEE/ACM Transactions, Volume 15, pp. 309 – 322 (2007).
[17] K. Ghaboosi, M. Latva-aho, Yang Xiao, and B. H. Khalaj, “Performance analysis of random access multi-hop ad hoc networks: An analytical approach”, Wireless Days (WD), 2nd IFIP, pp. 1 – 5 (2009).
[18] Hongqiang Zhai and Yugang Fang, “A Solution to Hidden Terminal Problem Over a Single Channel in Wireless AD HOC Networks”, Military Communications Conference, MILCOM 2006. IEEE, pp. 1 – 7 (2006).
[19] Chun-Chih Lo, Chao-Yu Kuo, Yi-Hung Huang, Kuan-Cheng Lin, and Yen-Ping Chu, “A Study on Hidden Receiver Problem in Mobile Ad Hoc Networks”, Wireless and Mobile Communications, ICWMC '08. The Fourth International Conference, pp. 49 – 54 (2008).
[20] Tang Yong and Man-yuan Zhou, “Study of AD HOC Network Access Single-Channel MAC Protocol and Hidden/Exposed Terminal”, Genetic and Evolutionary Computing, WGEC '09. 3rd International Conference, pp. 689 – 692 (2009).
[21] T. Watanabe, K. Naito, K. Mori, and H. Kobayashi, “Study of local alternative ad hoc routing protocol for the exposed terminal problem”, Intelligent Signal Processing and Communications, ISPACS '06. International Symposium, pp. 55 – 58 (2006).
[22] K. Ghaboosi, M. Latva-aho, and Yang Xiao, “Receiver blocking problem in mobile ad hoc networks: Challenges & solutions”, Wireless Days, WD '08. 1st IFIP, pp. 1 – 5 (2008).
[23] Jie Xu, Yuming Jiang, and A. Perkis, “Towards Analysis of Intra-flow Contention in Multi-hop Wireless Networks”, Mobile Ad-hoc and Sensor Networks (MSN), Sixth International Conference on, pp. 176 – 184 (2010).
[24] Hongqiang Zhai, Xiang Chen, and Yuguang Fang, “Alleviating intra-flow and inter-flow contentions for reliable service in mobile ad hoc networks”, Military Communications Conference, MILCOM 2004. IEEE, Volume 3, pp. 1640 – 1646 (2004).
[25] S. J. Lee and M. Gerla, “Dynamic Load Aware Routing in Ad Hoc Networks”, in Proc of IEEE ICC (2001).
[26] S. B. Lee and A. T. Campbell, “HMP: Hotspot Mitigation Protocol for Mobile Ad Hoc Networks”, in 11th IEEE/IFIP International Workshop on Quality of Service (2003).
[27] Z. Ye, D. Berger, P. Sinha, S. Krishnamurthy, M. Faloutsos, and S. K. Tripathi, “Alleviating MAC Layer Self-Contention in Ad-Hoc Networks”, in Proc. Of ACM MOBICOM 2003 Poster (2003).
[28] C. Li and E. Knightly, “Coordinated Multi-hop Scheduling: A Framework for End-to-End Services”, IEEE/ACM Transactions on Networking, pp. 776 – 789 (2002).
[29] V. Kanodia, C. Li, A. Sabharwal, B. Sadeghi and E. Knightly, “Distributed Multi-Hop Scheduling and Medium Access with Delay and Throughput Constraints”, in Proc. of ACM MobiCom (2001).
[30] IEEE 802.11 Working Group, “Part Ⅱ: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications”, ANSI/IEEE Std. 802.11 (1999).
[31] S. L. Beuerman and E. J. Coyle, “The delay characteristics of CSMA/CD networks”, Communications, IEEE Transactions, Volume 36, pp. 553 – 563 (1988)
[32] Peng Xiangyu, Jiang Letian, and Xu Guozhi, “Performance Improvement for the Basic Access Mechanism of WLAN with Noise Detection”, Circuits and Systems for Communications, ICCSC 2008. 4th IEEE International Conference, pp. 353 – 357 (2008)
[33] Kaixin Xu, M. Gerla, and Sang Bae, “How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks”, Global Telecommunications Conference, GLOBECOM '02. IEEE, Volume 1, pp. 72 – 76 (2002).
[34] R. Bruno, M. Conti, and E. Gregori, “IEEE 802.11 optimal performances: RTS/CTS mechanism vs. basic access”, Personal, Indoor and Mobile Radio Communications, The 13th IEEE International Symposium on, Volume 4, pp. 1747 – 1751 (2002).
[35] Chien-Min Wu and Ting-Chao Hou, “The impact of RTS/CTS on performance of wireless multihop ad hoc networks using IEEE 802.11 protocol”, Systems, Man and Cybernetics, IEEE International Conference, Volume 4, pp. 3558 – 3562 (2005).
[36] S. A. Chowdhury, M. T. Islam, F. T. Jaigirdar, M. R. U. Faruqui, and S. Al Noor, “Performance study and simulation analysis of CSMA and IEEE 802.11 in wireless sensor networks and limitations of IEEE 802.11”, Computers and Information Technology, ICCIT '09. 12th International Conference, pp. 431 – 436 (2009).
[37] Y. Hu, T. Luo, and J. Shen, “An Improvement of the Route Discovery Process in AODV for Ad Hoc Network”, Communications and Mobile Computing (CMC), International Conference, Volume 1, pp. 458 – 461 (2010).
[38] M. Bouhorma, H. Bentaouit, and A. Boudhir, “Performance Comparison of Ad-Hoc Routing Protocols AODV and DSR”, Multimedia Computing and Systems, ICMCS '09. International Conference, pp. 511 – 514 (2009).
[39] X. Li and L. Cuthbert, “Stable Node-Disjoint Multipath Routing with Low Overhead in Mobile Ad Hoc Networks”, Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, pp. 184 – 191 (2004).
[40] S. Sethi and S. K. Udgata, “IMAODV: A Reliable and Multicast AODV Protocol for MANET”, Wireless Communication and Sensor Networks (WCSN) (2009).
[41] Z. Zhai, Y. Zhang, M. Song, and G. Chen, “A Reliable and Adaptive AODV Protocol Based on Cognitive Routing for Ad Hoc Networks”, Advanced Communication Technology (ICACT), The 12th International Conference. Volume 2, pp. 1307 – 1310 (2010).
[42] B. Li, Y. Liu, and G. Chu, “Improved AODV Routing Protocol for Vehicular Ad Hoc Networks”, Advanced Computer Theory and Engineering (ICACTE), 3rd International Conference, Volume 4, pp. V4-337 – V4-340 (2010).
[43] M. P. Tahiliani, K. C. Shet, and T. G. Basavaraju, “Performance Evaluation of TCP Variants over Routing Protocols in Multi-hop Wireless Networks”, Computer and Communication Technology (ICCCT), pp. 387 – 392 (2010).
[44] Y. Xiao and X. Yin, “Performance Modeling and Analysis of IEEE 802.11 MAC Protocol in Multihop Ad Hoc Networks”, Wireless Communications Networking and Mobile Computing (WiCOM), 6th International Conference, pp. 1 – 5. (2010).
[45] M. Walia and R. K. Challa, “Performance Analysis of Cross-Layer MAC and Routing Protocols in MANETs”, Computer and Network Technology (ICCNT), pp. 53 – 59 (2010).
[46] X. Liu and S. Tarek, “Throughput Analysis of IEEE 802.11 Multihop Ad Hoc Wireless Networks underSaturation Condition”, Computers and Communications (ISCC), IEEE Symposium, pp. 245 – 248 (2010).
[47] X. M. Zhang, W. B. Zhu, N. N. Li, and D. K. Sung, “TCP Congestion Window Adaptation Through Contention Detection in Ad Hoc Networks”, Vehicular Technology, IEEE Transactions, Volume 59, pp. 4578 – 4588 (2010).
[48] Y. Hirano, S. Jain, and D. Raychaudhuri, “Chain Effect of Route Recoveries and MAC Layer Collisions in Wireless Multi-hop Networks”, Wireless Communications and Networking Conference (WCNC), pp. 452 – 457 (2011).
[49] S. Zheng, “Performance Study of Cooperative Routing Metric for Multi-Hop Wireless Networks”, Vehicular Technology Conference (VTC Spring) IEEE 73rd, pp. 1 – 5 (2011).
[50] M. Megha and H. Bechir, “An Improved IEEE 802.11 MAC Protocol for Wireless Ad-Hoc Networks with Multi-Channel Access Capabilities”, High Performance Computing and Simulation (HPCS), International Conference, pp. 162 – 168 (2011).
[51] L. Hanzo II and R. Tafazolli, “Admission Control Schemes for 802.11-Based Multi-Hop Mobile Ad Hoc Networks: a Survey”, Communications Surveys & Tutorials, IEEE, Volume 11, pp. 78 – 108 (2009).
[52] L. Yang, X. F. Zhang, and Y. S. Liu, “Analyzing and Improving the TCP Flow Fairness in 802.11 Based Ad Hoc Networks”, Wireless Communications & Signal Processing, WCSP 2009. International Conference, pp. 1 – 5 (2009).
[53] K. Fall and K. Varadhan, “Ns Notes and Documentation. LBNL”, http://www.mash.cs.berkeley.edu/ns/ (1998).