||Multi-channel MAC Protocols with Bandwidth Utilization Enhancement in Wireless Ad Hoc Networks
||Department of Computer Science and Information Engineering
||近年來，發展多頻道媒體存取協定已受到極大的關注與討論，並被認為是開發頻寬利用率的有效方法。在發展多頻道通訊協定時所遭遇最大的挑戰便是主機會面問題(Rendezvous Problem)與多頻道隱藏節點問題(Multi-Channel Hidden Terminal Problem)。為解決會面問題，有一些研究的作法，是讓所有主機週期性地在特定頻道的ATIM Window共同聚集，以安排資料交換的頻道，這樣的做法統稱Control Period Based(CPB)，然而，這樣的作法會造成其它頻道ATIM Window的頻寬利用率降低。為改善CPB的頻寬利用率，另一STEPWISE的頻道模型被提出，其以階梯式的安排使得各頻道上的ATIM Window得以錯開，傳送節點能透過頻道對應函數取得接收節點所在的頻道，於接收者的頻道安排資料交換的時槽，但此類做法當遭遇網路頻道流量不均(Channel Traffic Unbalance Problem)時，將導致少數頻道壅擠，而其他頻道卻閒置的情形。
||Multi-channel MAC protocols have recently attracted significant attention in wireless networking research because they possess the ability to boost the capacity of wireless ad hoc networks. However, the common challenges in developing multi-channel MAC protocol are the Multi-channel Hidden Terminal (MHT) problem and the Rendezvous problem. To avoid the two problems, a typical solution  proposed in literature is the CPB-based channel model which arranges an ATIM (Ad hoc Traffic Indication Messages) window in each beacon interval and asks all stations switch to the ATIM window of a predefined channel to cope with the rendezvous problem. Though all stations can negotiate the communication schedules in an ATIM window, however, the ATIM windows of all channels other than the predefined channel cannot be used for data exchange, leading to low channel utilization.
To prevent the low utilization of ATIM windows as found in CPB-based channel model, a STEPWISE Channel Model is proposed in literature to fully utilize the ATIM window each channel. However, there exists the unbalanced traffic problem where some busy channels have contention and collision problems while the other idle channels have low channel utilization.
This thesis presents two multi-channel MAC protocols. To improve the channel utilization problem as found in CPB-based channel model, this thesis proposes an ECU-MAC aims to increase the channel utilization and improve the network throughputs. The main idea of the proposed ECU-MAC is to exploit the bandwidth resource of ATIM windows of all channels for exchanging data such that the network throughput and channel utilization can be improved. As a result, the transmission delay can be significantly reduced. Performance evaluation and analytical results reveal that the proposed ECU-MAC outperforms existing MMAC and DCA protocols in terms of network throughput and average packet delay.
This thesis also applies the STEPWISE channel model but improves the channel utilization by migrating the traffics from busy channels to the idle channels. The key concept of HSR-MAC is to construct the urgent zones of the idle channel and then migrate the traffics of busy channels to the urgent zones. As a result, the HSR-MAC could disperse the traffic from busy channel to idle channel and hence significantly improve the network throughputs. Compared with existing multi-channel MAC protocols, the proposed multi-channel MAC protocols prevents the MCHT and Rendezvous problems while improving the network throughput.
||Table of Contents IV
List of Figures VI
List of Tables VIII
Chapter 1 Introduction 1
Chapter 2 Related Work 5
Chapter 3 The ECU-MAC Protocol 8
3.1 Network Environment and Problem Statement 8
3.1.1 Channel Model and Assumptions 8
3.1.2 Problem Statement 10
3.2 The ECU-MAC Protocol 13
3.2.1 The Basic Concept of ECU-MAC 14
3.2.2 Deaf Terminal Problem (Announce Phase) 17
3.2.3 Fairness for Data Channel Access 18
3.2.4 Rendezvous Enhancement (RE) Scheme 20
3.3 Throughput Analysis 21
3.3.1 Markov Chain Model 22
3.3.2 Throughput Analysis 24
3.4 Performance Study 25
3.4.1 Simulation Results 26
3.5 Summary 38
Chapter 4 The HSR-MAC Protocol 40
4.1 The Applied STEPWISE Channel Model 40
4.2 Network Environment and System Model 42
4.2.1 Motivation 42
4.2.2 System Model 43
4.2.3 Problem Formulation and Goal 44
4.3 The HSR-MAC Protocol 47
4.3.1 Data Slot State 47
4.3.2 The Design of Negotiation and Data Exchange Stages 51
18.104.22.168 Negotiation Stage 52
22.214.171.124 Data Exchange Stage 53
126.96.36.199 The HSR-MAC Algorithm 53
4.4 Performance Evaluation 56
4.4.1 Evaluation Environment 56
4.4.2 Evaluation Results 56
4.5 Summary 66
Chapter 5 Conclusions 67
List of Figures
Figure 2.1: The operation of negotiation and data exchange in MMAC 5
Figure 3.1: The channel model of our proposed protocol. 9
Figure 3.2: State diagram of sender, receiver and other stations. 14
Figure 3.3: Negotiation Procedure on the channel hneg 16
Figure 3.4: Three conditions in the Channel-Switching mode 17
Figure 3.5: Markov chain for the backoff window size 23
Figure 3.6: Aggregate Throughput vs. Packet Arrival Rate in a single-hop network 28
Figure 3.7: Average Packet Delay vs. Packet Arrival Rate in a single-hop network 30
Figure 3.8: Aggregate Throughput vs. Packet Arrival Rate in a multi-hop flow network 32
Figure 3.9: Average Packet Delay vs. Packet Arrival Rate in a multi-hop flow network 33
Figure 3.10: Channel Utilization/Control-Data Packet Ratio vs. Packet Arrival Rate 35
Figure 3.11: Average Packet Delay vs. Negotiation Window Size 36
Figure 3.12: Normalized Throughput vs. Number of Mean Nodes 37
Figure 3.13: Average Packet Delay vs. Number of Mean Nodes 38
Figure 4.1: The example of the STEPWISE channel model 41
Figure 4.2: The example of frame structure 44
Figure 4.3: An example of the next function 49
Figure 4.4: An example of urgent zone concept and SM 51
Figure 4.5: An example of Negotiation and Date-Exchange States 53
Figure 4.6: The state diagram of the sender in HSR-MAC 54
Figure 4.7: The state diagram of the receiver in HSR-MAC 54
Figure 4.8: The procedure of HSR-MAC Protocol 55
Figure 4.9: The comparison of MMAC, SMC-MAC and HSR-MAC in terms of throughput by varying offered traffics 58
Figure 4.10: The comparison of MMAC, SMC-MAC and HSR-MAC in terms of network throughput by varying the offered traffics 58
Figure 4.11: The comparison of MMAC, SMC-MAC and HSR-MAC in terms of average control overhead by varying number of one-hop neighbors 59
Figure 4.12: Data slot utilization of each channel at each second 60
Figure 4.13: The comparison of SMC-MAC and HSR-MAC in terms of channel utilization by varying channel-based traffic balance index 61
Figure 4.14: The comparison of channel utilization by varying station-based traffic balance index 62
Figure 4.15: The comparison of SMC-MAC and HSR-MAC in terms of channel utilization by varying the value of P 63
Figure 4.16: The comparison of network throughput by varying the offered traffics 64
Figure 4.17: The comparison of MMAC, SMC-MAC and HSR-MAC in terms of average packet delay by varying offered traffic 65
Figure 4.18: The comparison of packet drop ratio by varying delay bound 66
List of Tables
Table 3.1: The Abbreviations of Compared Mechanisms 25
Table 3.2: Simulation Parameters 25
Table 4.1: Simulation Parameters 56
|| P. Gupta and P. R. Kumar, “The capacity of wireless network,” IEEE Transaction on Information Theory, vol. IT-46, no. 2, pp. 388-404, 2000.
 IEEE Std 802.11b-1999, Part 11: wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High Speed Physical Layer Extension in the 2.4 GHz Band, 1999.
 IEEE Std 802.11a-1999, Part 11: wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High Speed Physical Layer Extension in the 5 GHz Band, 1999.
 IEEE Std 802.11-1999, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999.
 J. Lee, J. Mo, T.-M. Trung, J. Walrand and H. W. So, “Design and Analysis of a Cooperative Multichannel MAC Protocol for Heterogeneous Networks,” IEEE Transaction on Vehicular Technology, vol. 59, no.7, pp.3536-3548, 2010.
 S.-L. Wu, C.-Y. Lin, Y.-C. Tseng and J.-P. Sheu, “A New Multi-channel MAC Protocol with On-demand Channel Assignment for Multi-hop Mobile Ad Hoc Networks,” The International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN), Dec. 2000, pp.232-237.
 S.-L. Wu, Y.-C. Tseng, C.-Y. Lin and J.-P. Sheu, “A Multi-channel MAC Protocol with Power Control for Multi-hop Mobile Ad Hoc Networks,” Computer Journal, vol. 45, no.1, pp. 101-110, 2002.
 J. Shi, T. Salonidis and E. W. Knightly, “Starvation Mitigation through Multi-channel Coordination in CSMA Multi-hop Wireless Networks,” The ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2006, pp. 31-43.
 K. Liu and X. Xing, “A Multichannel Reservation Multiple Access Protocol for Mobile Ad Hoc Networks,” The IEEE International Conference on Communications (ICC), 2008, pp. 3176–3180.
 M. Seo, Y. Kim, and J. Ma, “Multi-channel MAC Protocol for Multihop Wireless Networks: Handling Multi-channel Hidden Node Problem Using Snooping,” The IEEE Military Communications Conference (MILCOM), 2008, pp. 1–7.
 J. Chen and Y.-D. Chen, “AMNP: Ad Hoc Multichannel Negotiation Protocol for Multihop Mobile Wireless Networks,” The IEEE International Conference on Communications (ICC), vol. 6, June 2004, pp. 3607-3612.
 T. Luo, M. Motani, and V. Srinivasan, “Altruistic Cooperation for Energy-efﬁcient Multi-channel MAC Protocols,” The ACM International Conference on Mobile Computing and Networking (MOBICOM), 2007, pp. 322–325.
 T. Luo, M. Motani, and V. Srinivasan, “Analyzing DISH for Multichannel MAC Protocols in Wireless Networks,” The ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2008, pp. 43–52.
 T. Luo, M. Motani, and V. Srinivasan, “Cooperative Asynchronous Multichannel MAC: Design, Analysis, and Implementation,” IEEE Transactions on Mobile Computing, vol. 8, no. 3, pp. 338–352, 2009.
 J. So and N. H. Vaidya, “Multi-channel MAC for Ad Hoc Networks: Handling Multi-channel Hidden Terminals Using a Single Transceiver,” The ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2004, pp. 222–233.
 S.-C. Lo and C.-W. Tseng, “A Novel Multi-channel MAC Protocol for Wireless Ad Hoc Networks,” The IEEE Vehicular Technology Conference (VTC), 2007, pp. 46–50.
 J. Zhang, G. Zhou, C. Huang, S. H. Son, and J. A. Stankovic, “TMMAC: An Energy Efficient Multi-channel MAC Protocol for Ad Hoc Networks,” The IEEE International Conference on Communications (ICC), 2007, pp. 3554–3561.
 C. Son, N.-H. Lee, B. Kim, and S. Bahk, “MAC Protocol Using Asynchronous Multi-channels in Ad Hoc Networks,” The IEEE Wireless Communications and Networking Conference (WCNC), 2007, pp. 401–405.
 W.-T. Chen and J.-C. Liu and T.-K. Huang and Yu-Chu Chang, “TAMMAC: An Adaptive Multi-channel MAC Protocol for MANETs,” IEEE Transactions on Wireless Communications, vol. 7, no. 11, pp. 4541–4545, 2008.
 G. Bianchi, “Performance Analysis of The IEEE 802.11 Distributed Coordination Function,” IEEE Journal on Selected Areas in Communications, vol. 18, no.3, pp. 535-547, 2000.
 N. C. Lan, C. Y. Lin, C. W. Chen, C. Y. Chang, “A Stepwise Multi-Channel MAC Protocol for Cognitive Radio Networks,” The 2011 Cross-Strait Conference on Information Science and Technology and iCube (CSCIST 2011 and iCube 2011), Taiwan, Dec. 2011.
 A. Tzamaloukas and J. Garcia-Luna-Aceves, “Channel-Hopping Multiple Access,” IEEE International Conference on Communications (IEE ICC), vol. 1, pp. 415–419, 2000.
 F. Hou, L. X. Cai, X. (Sherman) Shen and J. Huang, “Asynchronous Multichannel MAC Design With Difference-Set-Based Hopping Sequences,” IEEE Transactions on Vehicular Technology (IEEE TVT), vol. 60, no. 4, pp. 1728-1739, May. 2011.
 W. H. Liao, K. P. Shih, W. C. Chung, “Multi-channel Medium Access Control Protocol with Channel Distribution for Mobile Ad Hoc Networks,” IET Communications, vol. 3, no. 12, pp. 1821-1831, Dec. 2009
 P. Bahl, R. Chandra, and J. Dunagan, “SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-hoc Wireless Networks,” The 5th ACM international symposium on Mobile ad hoc networking and computing (ACM MobiHoc), pp. 216–230, 2004.
 K. Bian, J.-M. Park, and R. Chen, “A Quorum-based Framework for Establishing Control Channels in Dynamic Spectrum Access Networks,” The 15th Annual International Conference on Mobile Computing and Networking (MobiCom), pp. 25–36, 2009.
 H. R. Tsai, C. C. Chen, C. T. Chang, C. Y. Chang, “SMC-MAC: An Efficient Stepwise Multi-channel MAC Protocol for Ad Hoc Networks,” The 2011 Cross-Strait Conference on Information Science and Technology and iCube (CSCIST 2011 and iCube 2011), Taiwan, Dec. 2011.