Hop Count Distribution of Multi-Hop Transmissions in Wireless Ad Hoc Networks
Date Issued
2007
Date
2007
Author(s)
Kuo, Jia-Chun
DOI
en-US
Abstract
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.
Subjects
無線隨意網路
跳躍數分布
節點密度
以跳躍數為基準的定位法的準確性
網路的吞吐量
傳輸的延遲
wireless ad hoc network
hop count distribution
node density
estimation error of hop-count based localization
network throughput
transmission delay
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-F90921017-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):2898010a8f4375d9a53e117981f4bc72