臺灣博碩士論文加值系統

在行動隨意網路 (Mobile Ad hoc Network，簡稱為MANET) 中，媒體存取控制 (Medium Access Control) 主要在解決主機存取媒體時可能產生的競爭與碰撞問題。目前的媒體存取大都使用分散協調 (DCF) 的方式來避免碰撞，其方式為在發出訊號前每個主機會亂數產生一個延遲時間 (delay time)，稱為隨機訊框 (backoff) ，每個主機的延遲時間不同，因此能降低同時發出訊號而產生碰撞的機率，但是在高負載的狀態下，必須增加隨機訊框的長度(時間)以能容納更多的主機，這樣的方法雖然減少了碰撞機率，但卻帶來另一個問題，因增長等待時間而降低了傳輸效率。為了增加媒體存取的效率，目前已經有針對分散協調以動態調整隨機訊框的研究方向提出。針對提升媒體存取效率的目標，我們探討了以切割通道對分散協調 (DCF) 的影響，透過切割通道分離控制訊號 (control msg) 與資料訊框 (data frame)，減小控制通道 (control channel) 與資料通道 (data channel) 的頻寬，以較少的頻寬等待隨機訊框 (backoff) 時間，降低頻寬的浪費。
主機存取媒體時可能產生的競爭與碰撞問題。在發出訊號之前，主機會先檢查無線通道是否處於淨空狀態，為了避免碰撞發生，當載波偵測某個傳送者佔據通道時，會禁止本身發出訊號，如此將確保範圍內的通道僅被一對主機使用，而不會發生兩對以上主機的訊號互相干擾的情形。雖然媒體存取控制可以有效降低碰撞發生，然而在這樣的限制下，有傳送需求時，必須等待傳送者釋放通道才能取得通道使用權，並且在傳輸範圍內只能有一對主機可以傳送資料，而導致效能不佳的情況。我們針對分散協調機制效能不佳的問題提出資料通道共享的方法以達成重複使用資料通道的目標，來改進通道獨享的情形。透過分析暴露終端與802.11的協定控制，運用多通道技術，使控制訊號與資料訊號訊號在其專有的通道中傳送來達到通道同時被多對主機傳送資料的結果；除了共享通道的方法，為了提高多通道下的頻寬使用率，使訊號以管線化的方法達到最佳的協同作業，我們也推導出通道的頻寬配置比例，使整體傳輸效率 (throughput) 獲得明顯的改善。

In mobile ad-hoc networks (MANETs), the DCF protocol is commonly used to prevent collisions between nodes, each node has to wait for a random time period, called the backoff time, before it sends a handshaking signal to another node. However, when the number of nodes increases, the mean time of the random backoff time has to increase in order to reduce the probability of collisions. A performance degradation problem arises because a longer backoff time results in lower bandwidth utilization. A dynamically adjustable backoff time is proposed to improve bandwidth utilization. However, statistics of the network traffic for a period of time need to be determined in order to decide the backoff time dynamically; that is, collisions or low bandwidth utilization may occur before a proper mean value for the backoff time is set. In this paper, we address the problem of wasting bandwidth resources due to waiting for the backoff time and propose using multiple channels to achieve the goal of a high performance MAC design. In our design, a control channel and a data channel are used to improve bandwidth utilization. When the control channel waits for the backoff time, the data channel may transfer data. As a result, bandwidth utilization can be improved.
The IEEE 802.11 DCF protocol is commonly used for the medium access control layer (MAC) protocol to reduce the number of the collisions and contentions. mobile nodes have to wait for data transmission to be completed before they send data to anothers. As a result, performance degradation results from such limitations in the DCF mechanism. In this paper, we propose an overlapping data sub-channel method. The overlapping data sub-channel method can use a data sub-channel when the sender and receiver is currently using the same data sub-channel. In order to make the overlapping data sub-channel method work, we use the multiple channel technique to solve the interference problem. Although the overlapping data sub-channel method can increase the throughput, how to allocate the bandwidth of the control and data sub-channels to maximize bandwidth utilization is an important issue. we further propose a bandwidth allocation method to make the control signals and data signals in continuous frames be sent or received in a pipeline fashion.

目錄
摘要 I
Abstract III
誌謝 VI
目錄 VII
圖目錄 IX
表目錄 X
一、簡介 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究方法與貢獻 3
1.3.1分散協調 3
1.3.2暴露終端與多通道 4
二、知識背景與相關研究文獻 7
三、提出的方法 17
3.1 關於降低隨機訊框頻寬浪費 18
3.2 關於以重疊資料通道減少終端問題 31
3.2.1重疊的資料通道 31
3.2.2設計重疊的資料通道 34
3.2.3重疊資料通道的頻寬配置策略 42
四、模擬結果 44
4.1 分散協調的改善成果 44
4.2 重疊資料通道的改善成果 50
五、結論 55
參考文獻 57
Publication List of Chun-Liang Lai 61



圖目錄
Fig.1.1 隱藏終端問題與暴露終端問題 5
Fig.2.1 IEEE 802.11媒體存取三個階段 8
Fig.2.2 CSMA與交握協定的禁止範圍 11
Fig.2.3 訊號強度控制 12
Fig.2.4 單通道與多通道的多重存取 13
Fig.3.1 單通道的隨機訊框 19
Fig.3.2 兩種較差的多通道頻寬使用率 22
Fig.3.3 適當的多通道頻寬使用率 22
Fig.3.4 以多個資料通道的多重存取 26
Fig.3.5 增加RES的多通道通訊協定 27
Fig.3.6 降低控制通道的隨機訊框浪費的頻寬 28
Fig.3.7 控制通道切割為三個子通道，資料通道為k個子通道 29
Fig.3.8 兩主機依照訊號傳送範圍可分為三個區塊 33
Fig.3.9 單通道實做重疊資料通道的困難 36
Fig.3.10 提出的多通道模型 37
Fig.3.11 多資料通道模型 37
Fig.3.12 資料通道的重疊情形 43
Fig.4.1 頻寬比例模擬結果 47
Fig.4.2 不同主機數量在分散協調使用的頻寬 48
Fig.4.3 切割資料通道對傳輸效率的影響 49
Fig.4.4 主機數量對傳輸效率的影響 50
Fig.4.5 鄰居數量對頻寬使用率的影響 50
Fig.4.6 不同頻寬比例的傳輸效率 52
Fig.4.7 不同放大比例與主機密度的關係 53
Fig.4.8 不同數量的資料通道所表現的傳輸效率 54
Fig.4.9 不同數量的主機對傳輸效率的影響 54
Fig.4.10 速度對傳輸效率的影響 55


表目錄
Table.1 使用的常數列表 22
Table.2 舉例各訊號長度 25
Table.3 多子通道的訊號長度 30

參考文獻
[1]Institution of Electrical and Electronic Engineers. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Higher speed Physical Layer Extension in the 2.4 GHz Band, 1999.
[2]Charles E. Perkins, Pravin Bhagwat; “Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for Mobile Computers,” ACM SIGCOMM Computer Communication Review , Proceedings of the conference on Communications architectures, protocols and applications, vol. 24 issue 4, October 1994.
[3]S. Murthy, J.J. Garcia-Luna-Aceves; “An Efficient Routing Protocol for Wireless Networks,” Journal of ACM/Balzer Mobile Networks and Applications (Special Issue on Routing in mobile Communications Networks), pp. 183–197, 1996.
[4]J. Broch, D.B. Johnson, D.A. Maltz; “The Dynamic Source Routing Protocol for Mobile Ad Hoc Wireless Networks,” Mobile Ad-hoc Networks (manet), http://www.ietf.org/html.charters/manet-charter.html, Aug. 1998.
[5]C. Perkins, E. M. Royer, S. Das; “Ad hoc on Demand Distance Vector (AODV) Routing,” Mobile Ad-hoc Networks (manet), http://www.ietf.org/html.charters/manet-charter.html, Aug. 1998.
[6]Z. J. Haas, M. R. Pearlman; “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” Mobile Ad-hoc Networks (manet), http://www.ietf.org/html.charters/manet-charter.html, Nov. 1997.
[7]Elizabeth M. Belding-Royer; “Multi-Level Hierarchies for Scalable Ad Hoc Routing,” ACM Wireless Networks, vol. 9 issue 5, September 2003.
[8]Y.-B. Ko, N.H. Vaidya; “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Dallas, TX, pp.66–75, October 1998.
[9]Young Bae Ko, Nitin H. Vaidya; “Flooding-based Geocasting Protocols for Mobile Ad Hoc Networks,” ACM Mobile Networks and Applications, vol. 7 issue 6, December 2002.
[10]G. Bianchi; “Performance analysis of the IEEE 802.11 distributed coordination function” Selected Areas in Communications, IEEE Journal on Vol. 18, issue 3, pp.535-547, March 2000.
[11]Z. J. Haas, J. Deng; "On Optimizing the Backoff Interval for Random Access Schemes," IEEE Transactions on Communications, vol. 51, no. 12, pp. 2081-2090, December 2003.
[12]Chonggang Wang, Bin Li, Bo Li; Sohraby, K.; “An effective collision resolution mechanism for wireless LAN” Computer Networks and Mobile Computing, ICCNMC 2003. International Conference, pp.18-25,Oct 2003.
[13]J. Deng, P. K. Varshney, Z. J. Haas; "A New Backoff Algorithm for the IEEE 802.11 Distributed Coordination Function," Proc. of Communication Networks and Distributed Systems Modeling and Simulation (CNDS ''04), San Diego, CA, USA, January 18-21, 2004.
[14]Chonggang Wang, Weiwen Tang; “A probability-based algorithm to adjust contention window in IEEE 802.11 DCF” Communications, Circuits and Systems, 2004. ICCCAS 2004. vol. 1, pp.418-422, 27-29 June 2004.
[15]Daji Qiao, Shin, K.G.; “UMAV: a simple enhancement to the IEEE 802.11 DCF” System Sciences, Proceedings of the 36th Annual Hawaii International Conference on 6-9 Jan, pp. 9, 2003.
[16]P. Raptis, V. Vitsas; K. Paparrizos, P. Chatzimisios, A.C. Boucouvalas; “Packet Delay Distribution of the IEEE 802.11 Distributed Coordination Function” World of Wireless Mobile and Multimedia Networks, 2005. WoWMoM 2005. pp.299-304, June 2005.
[17]F. A. Tobagi, L. Kleinrock; “Packet Switching in Radio Channels: Part I - Carrier Sense Multiple-Access Modes and Their Throughput Delay Characteristics,” IEEE Transactions on Comm., vol. COM-23, no. 12, pp. 1400-1416, 1975.
[18]F. A. Tobagi, L. Kleinrock; “Packet Switching in Radio Channels: Part II - The Hidden Terminal Problem in Carrier Sense Multiple-Access Modes and the Busy-Tone Solution,” IEEE Transactions on Comm., vol. COM-23, no. 12, pp. 1417-1433, 1975.
[19]P. Karn; “MACA - a New Channel Access Method for Packet Radio,” ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, 1990.
[20]Vaduvur Bharghavan, Alan Demers, Scott Shenker, Lixia Zhang; “MACAW: a Media Access Protocol for Wireless LAN''s,” ACM SIGCOMM Computer Communication Review , Proceedings of the conference on Communications architectures, protocols and applications, vol. 24 issue 4, October 1994.
[21]Chane L. Fullmer, J. J. Garcia-Luna-Aceves; “Floor acquisition multiple access (FAMA) for packet-radio networks” ACM SIGCOMM Computer Communication Review , Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, Volume 25 Issue 4, October 1995.
[22]S. Singh and C. S. Raghavendra; “Power efficient MAC protocol for multihop radio networks,” in Proc. Int. Symp. Personal, Indoor Mobile Commun., 1998.
[23]V. Rodoplu and T. H. Meng, “Minimum energy mobile wireless networks,” IEEE J. Select. Areas Commun., vol. 17, pp. 1333–1344, Aug. 1999.
[24]S.-L. Wu, Y.-C. Tseng, and J.-P. Sheu; “Intelligent Medium Access for Mobile Ad Hoc Networks with Busy Tones and Power Control,” IEEE Journal on Selected Areas in Communications, 18(9):1647-1657, Sep. 2000.
[25]Eun-Sun Jung, Nitin H. Vaidya; “A power control MAC protocol for ad hoc networks,” Proceedings of the 8th annual international conference on Mobile computing and networking, September 2002.
[26]Alaa Muqattash, Marwan Krunz; “A single-channel solution for transmission power control in wireless ad hoc networks,” Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 2004.
[27]Zhenyu Tang, J. J. Garcia-Luna-Aceve; “Hop Reservation Multiple Access (HRMA) for Multi-channel Packet Radio Networks,” Proc. IEEE IC3N: Seventh International Conference on Computer Communications and Networks, Lafayette, Louisiana, October 1998.
[28]A. Muir, J. J. Garciauna-Aceves; “A Channel Access protocol for Multi-hop Wireless Networks with Multiple Channels,” Proceedings of the IEEE International Conference on Communications, pp. 1617-1621, 1998.
[29]Asis Nasipuri, Jun Zhuang, Samir R. Das; “A Multi-channel CSMA MAC Protocol for Multi-hop Wireless Networks,” Proc. of IEEE Wireless Communications and Networking Conference (WCNC''99), September 1999.
[30]A. Nasipuri, S. R. Das; “Multi-channel CSMA with Signal Power-based Channel Selection for Multi-hop Wireless Networks,” IEEE Vehicular Technology Conference (VTC), September 2000.
[31]S.-L. Wu, C.-Y. Lin, Y.-C. Tseng, J.-P. Sheu; “A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks,” IEEE Wireless Communications and Networking Conference (WCNC), September 2000.
[32]R. Garces, J. J. Garcia-Luna-Aceves; “Collision Avoidance and Resolution Multiple Access for Multi-channel Wireless Networks,” Proceedings of IEEE INFOCOM 2000, Tel-Aviv, Israel, vol.2, pp.595-602, 26-30 March 2000.
[33]Gang Qiang; Zengji Liu; Susumu Ishihara; Tadanori Mizuno; “CDMA-based Carrier Sense Multiple Access Protocol for Wireless LAN,” Vehicular Technology Conference, 2001 (IEEE VTS 53rd), vol. 2 , 6-9 May 2001.
[34]A. Tzamaloukas, J.J. Garcia-Luna-Aceves; “A Receiver-Initiated Collision-Avoidance Protocol for Multi-Channel Networks,” Proceedings of IEEE INFOCOM 2001.
[35]N. Jain, S. R. Das, A. Nasipuri; “A Multi-channel CSMA MAC Protocol with Receiver-Based Channel Selection for Multi-hop Wireless Networks,” Proc. of the 9th Int. Conf. on Computer Communications and Networks (IC3N), October 2001.
[36]Yu-Chee Tseng; Shih-Lin Wu; Chih-Yu Lin; Jang-Ping Sheu; “A multi-channel MAC protocol with power control for multi-hop mobile ad hoc networks” Distributed Computing Systems Workshop, pp.419 – 424, 16-19 April 2001.
[37]Haas, Z.J., Jing Deng; “Dual Busy Tone Multiple Access (DBTMA)-A Multiple Access Control Scheme for Ad Hoc Networks,” IEEE Transactions on Comm., vol. 50 no. 6, June 2002.
[38]Jiandong Li, Z. J. Haas, Min Sheng, Yanhui Chen; “Performance Evaluation of Modified IEEE 802.11 MAC for Multi-channel Multi-hop Ad Hoc Network,” 17th International Conference on Advanced Information Networking and Applications (AINA), March 2003.
[39]Jing Deng, Yunghsiang S. Han, Zygmunt J. Haas; “Analyzing Split Channel Medium Access Control Schemes with ALOHA Reservation,” Ad-Hoc, Mobile, and Wireless Networks - ADHOC-NOW ''03, S. Pierre, M. Barbeau, and E. Kranakis, Eds., 2003, vol. 2865 of Lecture Notes in Computer Science (LNCS), pp. 128-139, Springer-Verlag.
[40]Jungmin So, Nitin H. Vaidya; “Multi-channel MAC for Ad Hoc Networks: Handling Multi-channel Hidden Terminals Using a Single Transceiver,” Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 2004.
[41]Andrea Baiocchi, Alfredo Todini, Andrea Valletta; “Why a Multi-channel Protocol can Boost IEEE 802.11 Performance,” Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 2004.
[42]C.R. Lin and J.-S Liu.; “QoS Routing in Ad Hoc Wireless Networks,” IEEE Journal on Selected Areas in Communications, pp.1426-1438, August 1999.
[43]E. K. Wesel, Wireless Multimedia Communicaions: Networking Video, Voice, and Data. Reading, MA: Addison-Wesley, 1998.