A general framework for the capacity analysis of wireless ad hoc networks

Abstract

In this paper, we introduce a general framework for computing the throughput capacity of wireless ad-hoc networks under all kinds of information dissemination modalities. We consider point-to-point communication for unicast, muticast, broadcast and anycast routing under the physical model assumption. The general communication is denoted as $(n, m, k)$-cast where $n$ is the number of nodes in the network, $m$ is the number of destinations on $(n, m, k)$-cast group and $k(k leq m)$ is the number of destinations that receive packets from the source in each $(n, m, k)$-cast group. For example, $(m=k=1)$ and $(m=k=n)$ represent unicast and broadcast routings respectively. We demonstrate that the upper bound of throughput capacity is given by $O(sqrt{m}(sqrt{n}k)^{-1})$ bits/second. The lower bound of throughput capacity is computed as $Omega(sqrt{m}(nkd(n))^{-1})$, $Omega((nk{d}^{2}(n))^{-1})$ and $Omega(n^{-1})$ bits/second when $m=O(d^{-2}(n))$, $Omega(k) =(d^{-2}(n))=O(m)$ and $Omega(d^{-2}(n))=k$ respectively, where $d(n)$ is a network parameter. The upper bound capacity is achieved based on an $(n, m, k)$-cast tree constructed for routing and transport capacity while the lower bound capacity is achieved based on TDMA scheme and connected cell graph along $(n, m, k)$-cast tree.