| 摘要: | 「無線行動隨建即連網路」(wireless mobile ad hoc network, MANET) 是由一群具有無線傳輸裝置的行動主機所組成的通訊網路。行動主機彼此之間的通訊不需依賴基地台，而是藉由其他行動主機合作，以多段通訊 (multihop communication) 的 方式來達成在行動主機間傳遞訊息的目的。因此，這種網路可以不受時間、地點的限制，快速的由一群行動主機架構完成。無線傳輸媒體 (spectrum) 一般可分成單一頻道 (single-channel) 與多重頻道 (multi-channel) 兩種模式。網路的媒體存取層 (medium access control, MAC) 最主要的目的就是要增進媒體的使用效率。然而主要影響媒體使用效率的就是競爭與碰撞 (contention/collision)。在本篇論文中，我們將在這具有無線、行動且分散式的環境中，針對三種不同的環境，提出五種不同的協定來提昇媒體傳輸效率。這三種環境分別為 「單一頻道」, 「無座標式多重頻道」 (multi-channel without location awareness) 及「有座標式多重頻道」 (multi-channel with location awareness)。 我們知道在一定的區域內使用較小的發射功率可以讓同一時間更多行動主機使用相同的頻道。在單一頻道環境中，我們所設計的新協定 (protocol) 是藉由控制發射功率 (power control) 的大小，再結合傳統交換RTS/CTS 及 busy-tone 的機制，更進一步的提升頻道的使用效率。另外我們也討論分析使用有限段式 (discrete) 取代連續無段式 (continuous) 的調整發射功率，並且修改協定使其達到最佳的成本效益比。最後我們經由分析及實驗證明這個協定確實優於傳統協定大約兩倍的效能。 多重頻道的技術是另一個減輕媒體競爭與碰撞的方法。多重頻道比單一頻道的好處主要有三點：(1)系統總頻寬可以立即增加數倍， (2) 降低傳輸封包的碰撞機率，(3) 較容易支援QoS (quality of service)。雖然使用多重頻道有那麼多的好處，但是設計上除了要有良好的媒體存取機制外，還必須配合一套有彈性的頻道配置 (channel assignment) 機制，才能使多重頻道協定的效能發揮到極致。 在無座標式多重頻道環境中，我們設計一個具有動態頻道分配的協定，稱之為DCA (dynamic channel assignment)。DCA具有下列數個特性: (1)以On-Demand的方式分配頻道給需要通訊行動主機，(2) 系統提供給網路所需的頻道個數與網路的拓樸是無關的，(3) 此協定只需要交換少數的控制訊息(Control Messages)就可以同時完成媒體存取與頻道配置兩個功能，(4)行動主機不需要任何型式的時間同步(time synchronization)。經由分析與實驗得知DCA確實比其他協定較適合於無線行動隨建即連網路。另外，我們將控制發射功率的機制加入DCA，讓頻道重複使用率更加提高。經由實驗得知，效能大約比DCA提昇四成左右。 無線行動隨建即連網路既然是在一個固定區域上運作，因此行動主機所在位置便成為很重要的資訊。在最後一個環境有座標式多重頻道中，我們設計一個新的協定稱為GRID，它最大的特色就是利用位置資訊完成頻道的配置，行動主機完全不需負擔任何控制訊息的收送。在媒體存取方面，我們使用類似RTS/CTS的方式，保留媒體的使用權，這種方式的優點是行動主機間不需任何形式的時間同步，而且系統提供給網路頻道個數與網路的拓樸也是無關的。此外GRID所使用的頻道配置是靜態的。我們知道在現實狀況中，經常會有某些地區人口密集的狀況出現，如果只是使用簡單的靜態頻道配置，效率將會不好。因此我們提出借頻道的方式來達成動態是的頻道配置，經由實驗證明確實可以提昇不少效能。 The architecture of a wireless mobile ad hoc network (MANET) is formed by a cluster of mobile hosts and can be rapidly deployed without any established infrastructure or centralized administration. The channel model of MAC layer can be categorized as the single-channel model or the multi-channel model. In single-channel model, all mobile hosts operate on the single common channel for communication. In multi-channel model, the overall bandwidth is divided into several channels and every mobile host can operate any one or some of these channels for communication. One essential issue of MAC layer is to how to increase channel utilization while avoiding the hidden-terminal and the exposed-terminal problems. Therefore, this dissertation proposes five protocols to increase MAC performance in three major topics, that is, single-channel with power control, multi-channel without location awareness, and multi-channel with location awareness. It is well known that using smaller radio transmission power can increase channel reuse. In the first topic, we explore the possibility of combining the concept of power control with the RTS/CTS-based and busy-tone-based protocols to further increase channel utilization in the signle-channel. A sender will use an appropriate power level to transmit its packets so as to increase the possibility of channel reuse. The possibility of using discrete, instead of continuous, power levels is also discussed. Through analysis and simulations, we demonstrate the advantage of our new MAC protocol. Another approach to relieving the contention/collision problem is to utilize multiple channels. This dissertation also considers the access of multiple channels in a MANET with multi-hop communication behavior. Using multiple channels has several advantages. First, while the maximum throughput of a single-channel MAC protocol is limited by the bandwidth of the channel, the throughput may be increased immediately if a host is allowed to utilize multiple channels. Second, as shown in [6, 54], using multiple channels experiences less normalized propagation delay per channel than its single-channel counterpart, where the normalized propagation delay is defined to be the ratio of the propagation time over the packet transmission time. Therefore, this reduces the probability of collisions. Third, since using a single channel is difficult to support quality of service (QoS), it is easier to do so by using multiple channels [50]. In the second topic, we propose a new multi-channel MAC protocol DCA(Dynamic Channel Assignment), which is characterized by the following features: (i) it follows an 'on-demand' style to assign channels to mobile hosts, (ii) the number of channels required is independent of the network topology and degree, (iii) it flexibly adapts to host mobility and only exchanges few control messages to achieve channel assignment and medium access, and (iv) no form of clock synchronization is required. Compared to existing protocols, some assign channels to hosts statically (thus a host will occupy a channel even when it has no intention to transmit) [11, 34, 37], some require a number of channels which is a function of the maximum connectivity [11, 23, 34, 37], and some necessitate a clock synchronization among all hosts in the MANET [37, 67]. It is known that using smaller radio transmission power can increase channel reuse and thus channel utilization. It also saves the precious battery energy of portable devices and reduces co-channel interference with other neighbor hosts. Therefore, we combine the above DCA protocol with power control scheme for furthermore improving DCA performance. Since a MANET should operate in a physical area, it is very natural to exploit location information in such an environment. Therefore, in the third topic, we propose another MAC protocol GRID in the multi-channel system with exploiting position information. Its channel assignment is characterized by two features: (i) it exploits location information by partitioning the physical area into a number of squares called grids, and (ii) it does not need to transmit any message to assign channels to mobile hosts. Several channel assignment schemes have been proposed earlier [23, 28, 37, 54, 67], but none of them explore in the location-aware direction. Based on a RTS/CTS-like reservation mechanism, this medium access protocol does not require any form of clock synchronization among mobile hosts and is also a degree-independent protocol. In the above GRID protocol, channels are assigned to grids statically. In real world, however, some grids could be very crowded and thus 'hot,' while some could be 'cold.' Apparently, it will be more flexible if channels can be borrowed among grids to resolve the contention in hot spots. This has motivated us to investigate the possibility of dynamically assigning channels to grids. Based on the above protocol and this idea, we further proposed a new protocol, called GRID-B (read as GRID with channel borrowing). We propose four strategies for the sorting: sequential-sender-based borrowing, sequential-receiver-based borrowing, distance-sender-based borrowing, and distance-receiver-based borrowing. The basic idea is that we will assign to each grid a default channel, and a list of channels owned by its neighboring grids from which it may borrow. The purpose is twofold: (i) we dynamically assign channels to mobile hosts so as to take care of the load unbalance problem caused by differences among areas (such as hot and cold spots), and (ii) we sort channels based on mobile hosts' current locations so as to exploit larger channel reuse. In GRID, channels are assigned to grids statically, and we find that using a dynamic assignment in GRID-B can further improve the throughput of channels. |
