2021/04/19 by Varsha Dani, Aayush Gupta, Dani, Varsha +5 · 1 citation
Computer Science · #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2104.09096
openalex publication_date 2021/04/19 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We consider networks of small, autonomous devices that communicate with each\nother wirelessly. Minimizing energy usage is an important consideration in\ndesigning algorithms for such networks, as battery life is a crucial and\nlimited resource. Working in a model where both sending and listening for\nmessages deplete energy, we consider the problem of finding a maximal matching\nof the nodes in a radio network of arbitrary and unknown topology.\n We present a distributed randomized algorithm that produces, with high\nprobability, a maximal matching. The maximum energy cost per node is O(\log2\nn), where n is the size of the network. The total latency of our algorithm\nis O(n \log n) time steps. We observe that there exist families of network\ntopologies for which both of these bounds are simultaneously optimal up to\npolylog factors, so any significant improvement will require additional\nassumptions about the network topology.\n We also consider the related problem of assigning, for each node in the\nnetwork, a neighbor to back up its data in case of node failure. Here, a key\ngoal is to minimize the maximum load, defined as the number of nodes assigned\nto a single node. We present a decentralized low-energy algorithm that finds a\nneighbor assignment whose maximum load is at most a polylog(n) factor bigger\nthat the optimum.\n