Project topics and materials
Get Complete Project Material File(s) Now! »
The Round Weighting and Gathering Problem
The Minimum Time Gathering focus on the problem of routing a given demand from each node to the base station. Thus, the goal is completed when the last message reaches the BS and the protocol ends. This may not be the case for certain applications, where a permanent communication between the nodes is sent over time, i.e., messages are permanently created in their sources. This introduces a new type of model where traffic has to be allocated permanently, in a periodic way.
When the network is in a steady state, the relevant time-scale to focus on is the period. In our case, such a period is a sequence of round activations providing enough capacity for routing the flow of messages.
In other words, there is enough capacity for each node v to send b(v) messages, each message to be forwarded toward the sink, and the sink to receive v b(v) messages at each period. In particular, a given message may need several periods to reach its destination and the data rate provided to node v equals b(v) W , where W is the length of the period. A fair optimization of the transport capacity is therefore equivalent to minimizing W such that there is enough capacity to send a given demand at each node.
In this thesis, we address the relaxation of this problem in which a solution is no longer a sequence of rounds, but a continuous (no longer discrete) weight function w : R → R+ on the set of rounds R. In this case, w(R) represents how often round R should be activated in such a way that b(v)
messages are sent by each node v during each period, and W = P R∈R w(R).
The Round Weighting Problem (RWP) has been formalized in [KMP08], that jointly considers the multi-commodity flow problem and the weighted fractional coloring problem. In fact, they consider the problem for general demands b(u, v) for any ordered pair (u, v). Here we restrict ourselves to the gathering instances.
Now, we formally introduce the round weighting problem.
Relationship between gathering and round weighting
To get some idea of the relationship between the Round Weighting and the Minimum Time Gathering problems we present the example of figure 1.9. In this figure, we present the case of a network which is a path with n nodes numbered from 0 to n − 1. The base station is placed in node 0. The demand consists in one message placed in node n − 1. We suppose an asymmetrical interference model with parameters dT = dI = 1.
For the case of Minimum Time Gathering(see 1.9(a)) having 1 unit of demand in node n − 1 means that the message must be transmitted from node n − 1 to node BS = 0. The solution presented requires n − 1 time-steps. Indeed, we can observe that this solution is optimal. The solution consists of n − 1 rounds where the round i consists in one call transmitting the message between nodes n − i and n − i − 1.
For the case of the Round Weighting Problem(see 1.9(b)) having 1 unit of demand in node n − 1 means that we look for the minimum period W such that 1 message must be routed from node n−1 to BS in a period of length W. The solution proposed consists in a function of weights over the rounds w which is non-zero for three rounds denoted R1, R2 and R3. This rounds are defined as Ri = {j → j − 1 | j = i mod 3},i = 1, 2, 3 where j → j − 1 denotes a call between node j and node j − 1. The weight of each round is defined as Ri = 1 for i = 1, 2, 3 and 0 for all the other rounds. In this way, the associated capacity cw of each edge of the path is 1. Then, there exists a flow function satisfying the capacity cw of each node and transmits 1 unit of demand from n − 1 to BS. The total weight of the solution is W(w) = w(R1) + w(R2) + w(R3) = 3. Hence, we have that the solution routes 1/3 units per time-step from node n − 1 to BS. As a remark, we can observe that this solution is optimal.
Round Weighting Problem and Gathering in wireless net-
works with symmetrical interference In chapter 64 we considered the RWP for gathering instances. We present methods to obtain lower bounds for general topologies using cliques of calls. However, explicit lower bounds and optimal results are presented for grids with the base station placed either at the center or at the corner. A preliminary version has been presented in [GPRR08] for the case dsI = 2, dT = 1.
In this chapter, the base station is denoted g (as a reference of gateway).
Table of contents :
R´esum´e
Abstract
1 Introduction
1.1 Communication Models
1.1.1 General Models
1.1.2 Models studied in this thesis
1.2 Mimimum Time Gathering Problem
1.2.1 The model
1.2.2 Hardness results
1.2.3 A 4-approximation
1.2.4 Specific topologies
1.3 The Round Weighting and Gathering Problem
1.3.1 Model
1.3.2 Related Work
1.3.3 Hardness of Round Weighting
1.3.4 Relationship between gathering and round weighting
2 Summary of the results
2.1 Gathering radio messages in the path
2.1.1 Interference
2.1.2 Demand
2.1.3 Methodology
2.1.4 Results
2.2 Minimum delay Data Gathering in Radio Networks
2.2.1 Interference
2.2.2 Demand
2.2.3 Methodology
2.2.4 Results
2.3 Round weighting in the primary node interference model
2.3.1 Interference Model
2.3.2 Demand
2.3.3 Methodology
2.3.4 Results
2.4 Round Weighting Problem in wireless networks with symmetrical interference
2.4.1 Interference
2.4.2 Methodology
2.4.3 Results
2.5 Asymptotic Congestion Wireless Ad-Hoc and Sensor Networks
2.5.1 Methodology
2.5.2 Results
3 Gathering radio messages in the Path
3.1 Introduction
3.1.1 Background and motivation
3.1.2 Modeling aspects
3.1.3 Related work
3.1.4 Structure of the paper
3.2 Preliminaries
3.2.1 The model: definitions and notation
3.2.2 The Minimum Time Gathering Problem
3.3 Lower Bounds and Simple Protocols for the sink as an end-vertex
3.3.1 A first lower bound
3.3.2 Optimal Protocols for Pn, n 6 (p + 1)dT + 1
3.3.3 A simple gathering protocol
3.3.4 Case q = dT − 1 (dI = pdT + dT − 1)
3.4 Another lower bound and a 1+-approximation
3.4.1 Another lower bound
3.4.2 A 1+-approximation
3.5 Incremental Protocols
3.5.1 Construction of the Incremental Protocol
3.5.2 A gathering protocol when q = 0
3.5.3 Upper bound for incremental protocol
3.5.4 Case q + 1 and dT are relatively prime
3.5.5 Simple protocols
3.5.6 Existence of optimal incremental protocols
3.6 Gathering into an arbitrary vertex of the path
3.7 Conclusions
4 Minimum delay data gathering in radio networks
4.1 Introduction
4.1.1 Related Work
4.1.2 Our results
4.2 Preliminaries
4.2.1 Notations
4.2.2 Lower bound
4.3 Personalized Broadcasting Algorithms
4.3.1 Horizontal-Vertical broadcasting
4.3.2 +2 approximation
4.3.3 +1 approximation
4.4 Distributed Algorithm
4.4.1 Distributed Model
4.4.2 Basic Description of Distributed Algorith
4.4.3 Formal Description of Distributed Algorithm
4.5 Conclusion and Further Works
5 Round weighting in the primary node interference model
5.1 Introduction
5.2 Model
5.2.1 Interference Model: Matchings
5.3 One node with demand
5.3.1 Paths
5.3.2 Even Cycles
5.3.3 Odd Cycles
5.3.4 Special Cases
5.4 Multiple nodes with demands
5.5 Conclusions
6 Round Weighting Problem in wireless networks with symmetrical interference
6.1 Introduction
6.2 Related Work
6.3 Problem Statement
6.3.1 Interference model
6.3.2 Definitions
6.4 Lower Bounds
6.4.1 Lower Bounds using one call-clique
6.4.2 Lower Bounds using many call-cliques
6.4.3 Lower Bounds using Critical Edges
6.4.4 Relationship with Duality
6.5 Application in grids
6.5.1 Gateway in the middle: A lower bound
6.5.2 Gateway in the middle: An upper bound
6.5.3 Gateway in the corner: A lower bound
6.5.4 Gateway in the corner: An upper bound
6.6 Conclusion and perspectives
