廖婉君臺灣大學：電機工程學研究所郭嘉駿Kuo, Jia-ChunJia-ChunKuo2007-11-262018-07-062007-11-262018-07-062007http://ntur.lib.ntu.edu.tw//handle/246246/53534無線隨意網路是由許多個無線的移動節點以多重跳躍的方式所組成，而這樣一個網路不需要任何的基礎建設。當節點們彼此之間的距離夠近時，一個無線隨意網路就能夠自動地在任何時間任何地點形成。在這樣一個網路中，所有的傳輸都是以同儕對同儕的方式進行，所有的節點不但要傳送自己的資料封包，同時也要為網路中其它的節點來傳遞資料。 這篇論文的目的主要是研究在這樣一個網路下，傳輸所需要的跳躍數的分布情況，我們提出數學分析模型來分別探討不同的網路參數對於跳躍數的影響。首先，我們針對當網路節點密度很大時，在考慮節點有可能移動的情況下，封包被傳遞所需的跳躍數分布，接著，我們考慮一個比較普遍的情況，也就是當節點密度是任意值的時候，在這樣的條件下，分析所需要的數學難度以及所考慮的情況也更為複雜。在藉由數學分析得到結果以後，我們也藉著模擬的結果驗證了其分析的準確性。 除此之外，根據前面分析的結果，我們也延申探討在無線隨意網路下，以跳躍數為基礎的定位方法的準確性，根據我們的結果，在所有網路條件已知的情形下，我們可以利用數學分析來事前預知定位的精準度，以節省模擬所需花費的時間。同時，我們也進一步討論了網路傳輸的吞吐量和時間延遲，相較於之前許多的相關文獻，我們的研究成果提供了更為精準的結果。最後，對於未來可能出現的無線異質網路，我們也根據前面分析跳躍數分布的結果，討論了選擇傳輸模式的問題。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.Chapter 1 Introduction 1 1.1 Introduction to Ad Hoc Networks 1 1.2 Research about Ad Hoc Networks 2 1.3 Significance of Hop Count on Ad Hoc Networks 3 1.4 Motivation 4 1.5 Organization of the Dissertation 4 Chapter 2 Hop Count Distribution in Ad Hoc Networks with High Node Density 6 2.1 Introduction 6 2.2 System Model and Assumption 6 2.3 Hop Count Distribution for Flooding-based Packet Forwarding 8 2.3.1 Multi-hop Packet Forwarding via Flooding 8 2.3.2 Hop Count Distribution 9 2.4 Performance Evaluation 16 2.4.1 Analysis vs. Simulation 16 2.4.2 Impact of Node Mobility on Hop Count for Packet Delivery 19 2.5 Summary 22 Chapter 3 Hop Count Distribution in Ad Hoc Networks with Arbitrary Node Density 23 3.1 Introduction 23 3.2 System Model and Assumption 24 3.3 Modeling Hop Count Distribution 26 3.3.1 Per-Hop Progress 26 3.3.2 Connectivity of a Multi-hop Path 34 3.3.3 Probability Distribution of Required Hop Counts 35 3.4 Performance Evaluation 36 3.4.1 Expected Progress in One Hop 37 3.4.2 Probability that the Destination Is Reached with a Certain Hop Count 37 3.4.3 Delivery Ratio with Different Number of Neighbor Nodes 39 3.4.4 Expected Hop Count for Packet Transmissions 40 3.5 Summary 41 Chapter 4 Revisiting the Capacity and Delay in Wireless Ad Hoc Networks: A Hopping Approach 42 4.1 Introduction 42 4.2 Analytical Model 44 4.2.1 Network Model 44 4.2.2 Interference Model: Protocol Model 45 4.2.3 Definition of Capacity and Delay 45 4.3 Hop Progress 46 4.3.1 Hop Progress with Only One Effective Neighbor Node 47 4.3.2 Hop Progress with b Effective Neighbor Nodes 48 4.3.3 Hop Progress with Node Density n 48 4.4 Capacity and Delay of Wireless Ad Hoc Networks 53 4.4.1 Capacity and Delay in a Network 53 4.4.2 Impact of Power Control on the Network Capacity 58 4.4.3 Impact of Rate Adaptation on the Network Capacity 60 4.5 Summary 61 Chapter 5 Applications 62 5.1 Introduction 62 5.2 Analysis of Estimation Error of Hop-Count Based Localization Schemes 62 5.2.1 Introduction 62 5.2.2 A Probabilistic Model for Per-Hop Progress 63 5.2.3 Accuracy of Hop-Count Based Localization 65 5.3 Comparison of Different Flooding Schemes on Target Discovery 70 5.3.1 Network with High Node Density 70 5.3.2 Network with Arbitrary Node Density 74 5.4 Heterogeneous Wireless Networks: Modeling and Trade-off in Operation Mode Selection 80 5.4.1 Single Flow Scenario 80 5.4.2 Multiple Flows over a Single Chain 83 5.4.3 Multiple Flows over Different Routes 85 5.4.4 Operation Mode Selection for Dual-Mode Nodes 86 5.5 Summary 88 Chapter 6 Conclusion and Future Work 89 Reference 91 Publication List 961081477 bytesapplication/pdfen-US無線隨意網路跳躍數分布節點密度以跳躍數為基準的定位法的準確性網路的吞吐量傳輸的延遲wireless ad hoc networkhop count distributionnode densityestimation error of hop-count based localizationnetwork throughputtransmission delaythesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53534/1/ntu-96-F90921017-1.pdf