Power assignment in wireless ad hoc networks is an important issue of topology control which assigns power for each wireless node so that the induced communication graph satisfies some desired properties such as the connectivity and the energy spanner. In this paper, we study the problem of power assignment in order that its induced communication graph meets the following properties: (1) it is an energy-t-spanner which is energy efficient; (2) it is k-fault resistant which can withstand up to node failures where k？？？1; (3) the interference is minimal. We propose algorithms to address this problem. Both the theoretic analysis and the simulations in the paper prove that our algorithms can induce a k-fault resistant energy spanner and furthermore the interference is minimized. To the best of our knowledge, this is the first paper to study the power assignment problem simultaneously considering spanner properties, the fault tolerance, and the interference reduction. 1. Introduction Ad hoc networks are formed by autonomous nodes communicating via radio without any additional backbone infrastructure. Ad hoc networks have received significant attention in recent years due to their potential civilian and military applications. In wireless ad hoc networks, each node has limited resources such as energy, computing power, storage capacity; there are more challenges and problems compared with traditional fixed infrastructure networks. A fundamental problem in wireless ad hoc network is to find a power assignment so that the induced communication graph can satisfy some properties such as connectivity and energy spanner. An energy-t-spanner is a subgraph of , such that for any two nodes and in , there exists a path from to , whose energy is at most times the energy of a minimum-energy path from to in the original communication graph . The constant is called the power stretch factor. A small power stretch factor implies low energy spent by relay nodes in propagating a message, which is extremely useful for prolonging the lifetime of the network. Due to limited power sources, the idea of energy-t-spanner becomes an important design consideration in ad hoc networks. Much effort has been devoted to finding a power assignment that the induced graph is energy-t-spanner [1–3]. Nodes in a wireless network are typically battery powered, and it is infeasible or unable to recharge the device. Due to constrained power capacity, hostile deployment environment, and other factors, node failures are more likely to happen, which might cause network partitions and badly degrade
References
[1]
Y. Wang and X. Y. Li, “Minimum power assignment in wireless ad hoc networks with spanner property,” Journal of Combinatorial Optimization, vol. 11, no. 1, pp. 99–112, 2006.
[2]
H. Shpungin and M. Segal, “Near optimal multicriteria spanner constructions in wireless ad-hoc networks,” in Proceedings of the 28th Conference on Computer Communications (IEEE INFOCOM '09), pp. 163–171, Rio de Janeiro, Brazil, April 2009.
[3]
A. K. Abu-Affash, R. Aschner, P. Carmi, and M. J. Katz, “Minimum power energy spanners in wireless ad hoc networks,” in Proceedings of the 28th Conference on Computer Communications, pp. 1–6, San Diego, Calif, USA, March 2010.
[4]
H. Shpungin and M. Segal, “Near-optimal multicriteria spanner constructions in wireless Ad Hoc networks,” IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp. 1963–1976, 2010.
[5]
P. V. Rickenbach, R. Wattenhofer, and A. Zollinger, “Algorithmic models of interference in wireless Ad Hoc and sensor networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 1, pp. 172–185, 2009.
[6]
L. P. Chew, “There is a planar graph almost as good as the complete graph,” in Proceedings of the 2nd Symposium on Computational Geometry, pp. 169–177, Yorktown Heights, NY, USA, 1986.
[7]
R. E. N. Moraes, C. C. Ribeiro, and C. Duhamel, “Optimal solutions for fault-tolerant topology control in wireless ad hoc networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 12, pp. 5970–5981, 2009.
[8]
L. Li, L. Lian, and H. Bin, “Algorithms for k-fault tolerant power assignments in wireless sensor networks,” Science China Information Sciences, vol. 53, no. 12, pp. 2527–2537, 2010.
[9]
S. Indranil, K. S. Lokesh, K. G. Subhas, and K. P. Ranjeet, “Distributed fault-tolerant topology control in wireless multi-hop networks,” Wireless Networks, vol. 16, no. 6, pp. 1511–1524, 2010.
[10]
P. Carmi, M. Segal, M. J. Katz, and H. Shpungin, “Fault-tolerant power assignment and backbone in wireless networks,” in Proceedings of the 4th annual IEEE International Conference on Pervasive Computing and Communications Workshops, pp. 80–84, Washington, DC, USA, March 2006.
[11]
J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956.
[12]
S. Even and R. E. Tarjan, “Network flow and testing graph connectivity,” SIAM Journal on Computing, vol. 4, pp. 507–518, 1975.
[13]
G. Di Battista, R. Tamassia, and L. Vismara, “Output-sensitive reporting of disjoint paths,” Algorithmica, vol. 23, no. 4, pp. 302–340, 1999.
[14]
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 53, no. 8, pp. 41–47, 1959.
