In this chapter, we address the problem of gathering information in a specific node of a radio network when interference constraints are present. Nodes can communicate data using a radio device; we consider a synchronous time model, where time is divided into rounds. The interference constraints limit the possibility of simultaneous data communication of nodes to the same region of the network. The survey focuses on two interference models, the general interference model and the distance-2 interference model. We survey recent complexity results and approximation algorithms for several variants of the problem. We consider several interference scenarios, the uniform and non-uniform data models, different optimization parameters, and the off-line and online settings of the problem. The objective functions we consider are the minimization of maximum completion time, maximum flow time, and average flow time.
Bonifaci, V., Klasing, R., Korteweg, P., Stougie, L., Marchetti-Spaccamela, A. (2009). Data Gathering in Wireless Networks. In A. Koster, X. Muñoz (a cura di), Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks (pp. 357-377). Berlin : Springer [10.1007/978-3-642-02250-0_14].
Data Gathering in Wireless Networks
Bonifaci, V.;
2009-01-01
Abstract
In this chapter, we address the problem of gathering information in a specific node of a radio network when interference constraints are present. Nodes can communicate data using a radio device; we consider a synchronous time model, where time is divided into rounds. The interference constraints limit the possibility of simultaneous data communication of nodes to the same region of the network. The survey focuses on two interference models, the general interference model and the distance-2 interference model. We survey recent complexity results and approximation algorithms for several variants of the problem. We consider several interference scenarios, the uniform and non-uniform data models, different optimization parameters, and the off-line and online settings of the problem. The objective functions we consider are the minimization of maximum completion time, maximum flow time, and average flow time.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
