無線隨意網路中傳輸所需的跳躍數分布之研究

Hop Count Distribution of Multi-Hop Transmissions in Wireless Ad Hoc Networks

郭嘉駿(Jia-Chun Kuo)

指導教授 ： 廖婉君

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2007年)

https://doi.org/10.6342/NTU.2007.00710

摘要

無線隨意網路是由許多個無線的移動節點以多重跳躍的方式所組成，而這樣一個網路不需要任何的基礎建設。當節點們彼此之間的距離夠近時，一個無線隨意網路就能夠自動地在任何時間任何地點形成。在這樣一個網路中，所有的傳輸都是以同儕對同儕的方式進行，所有的節點不但要傳送自己的資料封包，同時也要為網路中其它的節點來傳遞資料。

這篇論文的目的主要是研究在這樣一個網路下，傳輸所需要的跳躍數的分布情況，我們提出數學分析模型來分別探討不同的網路參數對於跳躍數的影響。首先，我們針對當網路節點密度很大時，在考慮節點有可能移動的情況下，封包被傳遞所需的跳躍數分布，接著，我們考慮一個比較普遍的情況，也就是當節點密度是任意值的時候，在這樣的條件下，分析所需要的數學難度以及所考慮的情況也更為複雜。在藉由數學分析得到結果以後，我們也藉著模擬的結果驗證了其分析的準確性。

除此之外，根據前面分析的結果，我們也延申探討在無線隨意網路下，以跳躍數為基礎的定位方法的準確性，根據我們的結果，在所有網路條件已知的情形下，我們可以利用數學分析來事前預知定位的精準度，以節省模擬所需花費的時間。同時，我們也進一步討論了網路傳輸的吞吐量和時間延遲，相較於之前許多的相關文獻，我們的研究成果提供了更為精準的結果。最後，對於未來可能出現的無線異質網路，我們也根據前面分析跳躍數分布的結果，討論了選擇傳輸模式的問題。

關鍵字

無線隨意網路 ； 跳躍數分布 ； 節點密度 ； 以跳躍數為基準的定位法的準確性 ； 網路的吞吐量 ； 傳輸的延遲

並列摘要

A wireless ad hoc network is formed by wireless mobile nodes in a multi-hop manner, without any support of fixed infrastructures. As these nodes stay close enough, an ad hoc network can be created at anytime and anywhere. By multi-hop data transmissions, all nodes can communicate with each other quickly and efficiently. In such a network, all communications proceed in a peer-to-peer manner and these wireless mobile nodes play both transceivers and routers. Once the destination node is outside the transmission range of the source node, all data packets must be relayed hop-by-hop to reach the distant destination. Thus, we can understand the significance of hop counts for the performance of an ad hoc network.
This dissertation studies the required hop count distribution for source-destination pairs in an ad hoc network when packets are transmitted in a multi-hop manner. Specifically, we focus on the effect of network parameters (e.g., node density) on the hop progress and the connectivity of a multi-hop path. Then we further derive the required hop counts and apply the results to many applications of wireless ad hoc networks.
For an ad hoc network with high node density, hop progress is nearly equal to the transmission radius and no matter to which direction the next hop is, there is always a node available at the edge of the transmission range. In such an environment, the behavior of packet forwarding is analogous to the radiating ripples when one stone is dropped into a pond. Based on this observation, we propose an analytical model to obtain the probability distribution of hop count distance for a source-destination pair in the network given that all nodes may be roaming. The correctness and accuracy of the proposed model is validated via simulations.
As the node density is arbitrary, hop progress may not be equal to the transmission radius. The lower the node density, the smaller the hop progress. To derive the required hop count, we develop an analytical framework in a wireless ad hoc network with arbitrary node density. We start the derivation with the expected progress per hop and obtain the path connectivity probability in a network with shortest-path routing. Together with the derived per-hop progress and the path connectivity probability, we can express the probability distribution for the expected hop count in multi-hop wireless networks as the network parameters are given. Again, the accuracy of the model is verified by simulation results. In addition, based on the analytical model, we further study the capacity and delay of wireless ad hoc networks from another perspective: the viewpoint of hopping. By examining the correlation between the node density and hop progress, a clear asymptotic relationship between these two factors is provided. Then, we derive the scaling relationship between node density (or node number) and the performance metrics (i.e., throughput and delay) of wireless ad hoc networks.
Based on these analytical results, we study the deviation of the estimation error of hop-count based localization schemes. Compared with those existing work, our analytical model provides not only the expected progress in one hop but also the probability distribution of the hop progress. Such result can be used to estimate how accurate the hop-count based localization schemes are and save a lot of time for tedious simulation runs. Then, we evaluate the performance of different protocols and apply them to many applications in wireless ad hoc networks. We estimate the flooding cost and search latency of target location discovery commonly used in most existing on-demand ad hoc routing protocols (e.g., blind flooding, DSR and AODV), and the impact of different flooding schemes on the target discovery can also be obtained. The tradeoff relationship between flooding cost and search latency is demonstrated clearly. Finally, we apply the results to survey the mode selection problem to dual-mode nodes in heterogeneous wireless networks.

並列關鍵字

wireless ad hoc network ； hop count distribution ； node density ； estimation error of hop-count based localization ； network throughput ； transmission delay

參考文獻

[1] R. Bruno, M. Conti and E. Gregori, “Mesh Networks: Commodity Multihop Ad Hoc Networks,” IEEE Communication Magazine, pp.123-131, Mar, 2005.

[2] D. Cavalcanti, D. Agrawal, C. Cordeiro, B. Xie and A. Kumar, “Issues in Integrating Cellular Networks, WLANs and MANETs: A Futuristic Heterogeneous Wireless Network,” IEEE Wireless Communications, pp.30-41, Jun. 2005.

[3] Q. Song and A. Jamalipour, “Network Selection in An Integrated Wireless LAN and UMTS Environment Using Mathematical Modeling and Computing Techniques,” IEEE Wireless Communications, pp.42-48, Jun. 2005.

[4] V. Gazis N. Alonistioti and L. Merakos, “Toward A Generic “Always Best Coonected” Capability in Integrated WLAN/UMTS Cellular Mobile Networks (and Beyond),” IEEE Wireless Communications, pp.20-29, Jun. 2005.

[6] A. Zemlianov and G. Veciana, “Capacity of Ad Hoc Wireless Networks with Infrastructure Support,” IEEE Journal on Selected Areas in Communications, Vol.23, No.3, pp.657-667, Mar. 2005.