Algorithm design for wireless networks with minimized overhead costs

Wireless network performance is typically affected by overheads arising due to unique challenges of the wireless medium. The broadcast nature of the medium implies that the channel is shared among all nodes, thereby prohibiting simultaneous transmissions from neighbouring nodes. This results in contention and collision overheads which get compounded with the increase in the number of nodes, posing great challenges to network scalability. In a multihop scenario, overheads are incurred due to challenges associated with traditional distributed systems. This is aggravated by contention overheads described earlier which make it difficult to disseminate information on a large scale. In this work, the author studies the design of algorithms in wireless networks that incur zero or negligible overheads. The first problem addressed is differentiated channel access to provide quality of service (QoS) guarantees for real-time traffic. The author proposes a contention-tone based service differentiation scheme that leverages the benefits of out-of-band signaling to minimize collision probability. Using analytical and simulation results, the author shows that effective service differentiation can be achieved among the different traffic classes. The author addresses the issue of unfairness in two-way real-time traffic by using device specific differentiation in which the access point(AP) gets higher priority for channel access. The author shows that this results in equal opportunities for the AP and voice traffic, thereby resolving bottlenecks. Converse to its effect on contention, the broadcast nature provides implicit benefits for data dissemination as all transmitted data is shared among neighboring nodes. This feature has been referred to in existing literature as wireless broadcast advantage (WBA), which has been exploited for efficient protocol design to reduce transmission overheads. The author analyzes the performance benefits achievable purely by exploiting WBA in the context of network-wide broadcast. The analysis is focused on stateless broadcasting algorithms in which nodes decide on their forwarding behaviour based on information derived from overheard transmissions. The proposed approach categorizes the information available at the nodes into two distinct phases and identifies the performance benefits that can be attained from each. Based on insights obtained from the analysis, the author studies the design of stateless broadcasting algorithms in a multi-rate scenario. Subsequently, stateless algorithms that simultaneously reduce the broadcast latency as well as the percentage of forwarding nodes are proposed. The author's third contribution concerns the self-organization of a wireless network so as to provide performance guarantees. A design that reorganizes the network in order to exhibit small world properties is proposed. The author studies the use of long range directional beams between nodes to achieve reduction in path length across the network. The proposed algorithm centers around a new centrality measure, which is defined as the wireless flow betweenness (WFB). WFB can be computed individually at nodes based on traffic flow information obtained from neighborhood transmissions. Subsequently, long range beams from a fraction of nodes results in significant reduction in the average path length of the network. Thus, the proposed design exploits WBA and minimizes explicit overheads. The proposed measure involves recursive computation at nodes that results in information being propagated over multiple hops, which is unlike the stateless broadcasting mechanisms mentioned previously in which the information is limited to the local neighbourhood. Finally, the author studies the impact of WBA on the propagation of information over multiple hops. A setup in which nodes store and forward all information received implicitly from neighbourhood transmissions is considered and this results in the creation of a distributed cache across the network, which is termed broadcast cache. The author then analyzes the growth of the broadcast cache in terms of the smallest set of transmissions in the network, which is defined as the set of non-altruistic transmissions. The author obtains the feasibility conditions which determine whether WBA can be effectively utilized depending on the flow characteristics. The above problems are fundamental for a range of wireless network operations where it is imperative that overhead costs have to be minimized. The author's work also shows that the minimization of overhead costs can be achieved by a combination of algorithm design as well as the appropriate choice of parameters for the algorithm design.DOCTOR OF PHILOSOPHY (SCE