Issues in ad hoc networks: scaling laws, media access control, and power control
Additional Document Info
We present a brief account of three problems in wireless networks. First we address the issue of scalability. We show that, in theory, under a certain model of interference, a network with n nodes in a domain can provide at best a per-node throughput of O (1/n) bits/sec to random destinations, which further drops to O (1/n log n) if the nodes are randomly located. Then we present the results of an experimental investigation with IEEE 802.11 technology: The per node through-put follows a O (1/radic;n 1.68 ) scaling law which is considerably worse than what theory suggests is attainable. These results appear to suggest the need for an improved media access control protocol. So motivated, we present a new media access control protocol for ad hoc networks, called SEEDEX. It attempts to make reservations without explicitly doing so for each and every packet. The idea is for each node to use a random schedule. Nodes can inform each other about their schedules merely by exchanging the seeds of their pseudo random number generators. We present the design, as well as some simulation results comparing it with IEEE 802.11. Last we turn to the problem of power control in ad hoc networks. We present a new protocol called COMPOW, which is designed to find the lowest power level at which the entire network is connected. We provide the theoretical justification for it, and a solution of the architectural issues involved. Using a notion of parallel modularity at the network layer, this protocol provides a joint solution for both the routing and power control problems, which can be used in plug and play manner with any routing protocol which employs a routing table. It has been implemented in the Linux kernel.