On The k-hop Partial Connectivity in Finite Wireless Multi-hop Networks

Abstract

In this paper, we consider wireless multi-hop networks with a finite number of (ordinary) nodes randomly deployed in a given 2D area, and a finite number of gateways (infrastructure nodes) deterministically placed in the same area. We study the connectivity between the ordinary nodes and the gateways. In real applications, it is often desirable to limit the maximum number of hops between the ordinary nodes and the gateways in order to provide reliable services. On the other hand, requiring every ordinary node to be connected to at least one gateway imposes strong requirement on transmission range/power or the number of gateways. Therefore it is beneficial to allow a small fraction of ordinary nodes to be disconnected from the gateways so that the network is only partially connected. Based on the above two considerations, we propose the concept of k-hop partial connectivity, which is the fraction of ordinary nodes that are connected to at least one gateway in at most k hops. Analytical results are provided characterizing the k-hop partial connectivity. The research provides useful guidelines on the design of wireless multi-hop networks.