2nd International IEEE Conference on Communication System Software and Middleware

Research Article

On Optimal Performance in Mobile Ad hoc Networks

  • @INPROCEEDINGS{10.1109/COMSWA.2007.382619,
        author={ T. K. Patra and J. Kuri and P. Nuggehalli },
        title={On Optimal Performance in Mobile Ad hoc Networks},
        proceedings={2nd International IEEE Conference on Communication System Software and Middleware},
        keywords={Job shop scheduling  Media Access Protocol  Mobile ad hoc networks  Organizing  Processor scheduling  Routing  Telecommunication traffic  Throughput  Time division multiple access  Wireless networks},
  • T. K. Patra
    J. Kuri
    P. Nuggehalli
    Year: 2007
    On Optimal Performance in Mobile Ad hoc Networks
    DOI: 10.1109/COMSWA.2007.382619
T. K. Patra1,*, J. Kuri1,*, P. Nuggehalli 1,*
  • 1: Centre for Electronics Design and Technology Indian Institute of Science, Bangalore
*Contact email: tkpatra@cedt.iisc.emet.in, kuri@cedt.iisc.emet.in, pavan@cedt.iisc.emet.in


In this paper we are concerned with finding the maximum throughput that a mobile ad hoc network can support. Even when nodes are stationary, the problem of determining the capacity region has long been known to be NP-hard. Mobility introduces an additional dimension of complexity because nodes now also have to decide when they should initiate route discovery. Since route discovery involves communication and computation overhead, it should not be invoked very often. On the other hand, mobility implies that routes are bound to become stale resulting in sub-optimal performance if routes are not updated. We attempt to gain some understanding of these effects by considering a simple one-dimensional network model. The simplicity of our model allows us to use stochastic dynamic programming (SDP) to find the maximum possible network throughput with ideal routing and medium access control (MAC) scheduling. Using the optimal value as a benchmark, we also propose and evaluate the performance of a simple threshold-based heuristic. Unlike the optimal policy which requires considerable state information, the heuristic is very simple to implement and is not overly sensitive to the threshold value used. We find empirical conditions for our heuristic to be near-optimal as well as network scenarios when our simple heuristic does not perform very well. We provide extensive numerical and simulation results for different parameter settings of our model.