Analysis of Wireless Multi-Hop Broadcasting: Optimal and Approximate Solutions and Applications

In this work, we design and analyze transmission range assignments for broadcasting in wireless multi-hop networks. Moreover, we study different features of wireless networks. We consider network scenarios in which the exact location of the nodes is known and others where the nodes location is known probabilistically. For the former, we propose optimal and near-optimal algorithms to solve the Minimum-Energy Broadcasting problem for linear (one-dimensional) networks. We further extend our solutions to encompass cross networks, in which the nodes are located on two perpendicular lines. The proposed algorithms have polynomial-time complexity, and are shown to perform better than previously known algorithms (for some cases, they are the first polynomial-time solutions).For probabilistic networks, we propose a transmission range assignment such that for a given average total consumed power, the linear network is connected with high probability. We then analyze some features of these networks, including derivation of exact formulas for the probability of connectivity of any location of the network to the source, the hop-count probability mass function (pmf) of an arbitrary location of the network, and the pdf of the maximum coverage (last reachable distance from the source) for a given number of hops. The proposed analyses are applicable to networks with non-identical transmission range assignments, where the nodes are placed independently and identically according to a Poisson distribution with an arbitrary density function.Based on the derived formulas, we then propose localization and location verification methods. We show that our proposed localization method not only has a competitive performance for a range-free method, but also outperforms range-based methods with a local distance measurement error of 10% or more. Furthermore, the proposed location verification protocol is shown to have better results compared to the existing verification systems that also use the hop-count information. We also evaluate the proposed schemes in the presence of Rician fading and show that their performance is rather robust with respect to the change in the fading parameter.