|
Author(s):
|
Peng-Jun Wan, Illinois Institute of Technology, USA ; Lixin Wang, Illinois Institute of Technology, USA; Ophir Frieder, Illinois Institute of Technology, USA
|
|
Abstract:
|
In this paper, we present approximation algorithms for four group communications in multihop wireless networks subject to the physical interference constraint. These four group communications are broadcast, gathering, gossiping, and data aggregation. In broadcast, a distinguished source node sends a common packet to all other nodes. In gathering, a distinguished sink node collects a packet from every other node. In gossiping, every node broadcasts a packet to all other nodes. In data aggregation, a distinguished sink node collects the data aggregated from all the packets at the nodes other than the sink node. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one packet of a fixed size in each time-slot. The problem Minimum-Latency Broadcasting (respectively, Gathering, Gossiping, and Aggregation) Schedule seeks a gathering (respectively, gathering, gossiping, and aggregation) schedule of minimum latency in a multihop wireless network subject to the physical interference constraint. Under mild assumptions, all of approximation algorithms for these four problems have constant approximation factors. These algorithms are built upon a general technique which enables a unified graph-theoretic treatment of the scheduling subject to the physical interference constraint.
|
