Practical approximation solutions for fault-tolerant networks
Abstract
Wireless communication is increasingly being employed to transfer highly sensitive information. Systems such as ambient living assistance systems, emergency response systems employing wireless networks, contactless smart cards and military sensor networks all employ wireless communication to transmit potentially sensitive information,such as patient health information, banking or financial data or military information. Unlike wired networks, in which the link topology is fixed at the time the network is deployed, wireless networks have no fixed underlying topology. In addition, the relational disposition of wireless nodes is constantly changing. The temporary physical topology of the network is determined by the distribution of the wireless nodes, as well as the transmission rangeof each node. The ranges determine a communication graph, in which the nodes correspond to the transceivers and the edges correspond to the communication links. Unlike nodes in wired networks, wireless devices are typically equipped with limited energy supplies making energy efficiency one of the primary objectives in network design. Energy efficiency is especially important for networks where battery replacement is infeasible. In network design problems the goal is to select a ÒcheapÓ network that satisfies some prescribed property. Many fundamental properties can be characterized by degree demands (number of edges incident to a node), pairwise connectivity demands (number of disjoint paths between node pairs), network lifetime (the time it takes the first node to run out of its battery charge), nodes proximity, and others. The goal of this proposal is to investigate variants of ACTIVATION NETWORK DESIGN problems, where we seek an assignment a={a(v)=0 :vÀV}to the nodes, such that the activated graph G(a)= (V,E(a)) satisfies a given property, and the value a(V) =Àa(v) of the assignment is minimized. Such problems include node-weighted problems, min-power problems, installation problems, and more. We suggest to evaluate these problems practically by studying their approximability in terms of the slope parameter À, that is the maximum ratio between activating thresholds of the end nodes of an edge in the network. Besides finding a unifying algorithmic idea that generalizes and improves previous results, we expect to find practical tractable special cases in this new that can be implemented for real-life scenarios that require maintenance of the network for a long period of time.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- W911NF2210225
Entities
People
- Michael Segal
Organizations
- Army Contracting Command
- Ben-Gurion University of the Negev
- United States Army