2nd International ICST Workshop on Advances in Wireless Sensor Networks 2007

Research Article

Optimal Relay Node Fault Recovery

  • @INPROCEEDINGS{10.1109/MOBIQ.2007.4451039,
        author={ Fei  Che and Liang  Zhao and Errol  L.Lloyd},
        title={Optimal Relay Node Fault Recovery},
        proceedings={2nd International ICST Workshop on Advances in Wireless Sensor Networks 2007},
        keywords={Ad hoc networks  Collaboration  Computer networks  Costs  Energy consumption  Environmental factors  Fault tolerance  Government  Network topology  Relays},
  • Fei Che
    Liang Zhao
    Errol L.Lloyd
    Year: 2008
    Optimal Relay Node Fault Recovery
    DOI: 10.1109/MOBIQ.2007.4451039
Fei Che1,*, Liang Zhao1,*, Errol L.Lloyd1,*
  • 1: Department of Computer and Information Sciences University of Delaware Newark, DE 19716
*Contact email: fei@cis.udel.edu, zhaol@cis.udel.edu, elloyd@cis.udel.edu


Topology control problems are concerned with the assignment of power levels to the nodes of an ad-hoc network so as to maintain a specified network topology while minimizing the energy consumption of the network nodes. A two-tiered network model has been proposed recently for prolonging the lifetime and improving the scalability in ad-hoc sensor networks. Such networks however may suffer from the failure of relay nodes causing the network to lose functionality. While considerable attention has been given to the issue of fault-tolerance in such networks, all of the prior work has been concerned with maintaining a 2-connected network. In this paper, we consider an alternative approach, namely optimal relay node fault recovery, in which the network topology is required to be just 1-connected and when a relay node fails, we replace that node with a new relay node that is placed in a position such that the power level assigned to the new node is optimal. In general this will not be the original node position or power assignment. We study three versions of optimal relay node fault recovery that vary in the degree to which the original network nodes can be reconfigured (i.e. have adjustments made to their power levels) when adding the new relay node into the network. For each version, we provide a polynomial time algorithm that provides an optimal placement and power assignment for the new relay node.