|
Author(s):
|
Amitabha Ghosh, University of Southern California, USA ; Ozlem Durmaz Incel, Bogazici University, Turkey; Bhaskar Krishnamachari, University of Southern California, USA; Anil Vullikanti, Virginia Tech., USA
|
|
Abstract:
|
Fast and periodic collection of aggregated data is of considerable interest for mission-critical and continuous monitoring applications in sensor networks. In the many-to-one communication paradigm, known as convergecast, we consider applications wherein data packets are aggregated at each hop along a tree-based routing topology and focus on maximizing the data collection rate at a sink node. The primary hindrance in maximizing the data collection rate is the presence of interfering links. In this work, we employ TDMA scheduling and exploit the benefits of multiple frequency channels by assigning them appropriately to the parents of the routing tree in order to mitigate the effects of interference.
Our key result in the paper lies in proving that minimizing the schedule length for an arbitrarily deployed network (possibly even worst case) in the presence of multiple frequencies is NP-hard, and in designing approximation algorithms with provable performance guarantee for geometric networks. In particular, we design a constant factor approximation algorithm for networks modeled as unit disk graphs, where every node has a uniform transmission range, and a Delta(T)log n approximation algorithm for general disk graphs, where nodes could have different transmission ranges; $n$ is the number of nodes in the network and Delta(T) is the maximum node degree on a given routing tree T. We also prove that a constant factor approximation is achievable on unit disk graphs even for unknown routing topologies so long as the maximum degree of any node in the tree is bounded by a constant. To the best of our knowledge, these are the first approximation results on the optimal schedule length under multiple frequencies. Our other contributions are in showing that finding the minimum number of frequencies required to remove all the interfering links in an arbitrary network in NP-hard. We give an upper bound on the maximum number of such frequencies required and propose a polynomial time algorithm that minimizes the schedule length under this scenario. Finally, we evaluate our algorithms through simulations and show various trends in performance for different network parameters.
|
