The fundamental limits of broadcasting in dense wi

Authors: Giovanni Resta Paolo Santi

Publish Date: 2012/03/08

Volume: 18, Issue: 6, Pages: 679-695

PDF Link

Abstract

In this paper we investigate the fundamental properties of broadcasting in mobile wireless networks In particular we characterize broadcast capacity and latency of a mobile network subject to the condition that the stationary node spatial distribution generated by the mobility model is uniform We first study the intrinsic properties of broadcasting and present the RippleCast broadcasting scheme that simultaneously achieves asymptotically optimal broadcast capacity and latency subject to a weak upper bound on maximum node velocity and under the assumption of static broadcast source We then extend RippleCast with the novel notion of centercasting and prove that asymptotically optimal broadcast capacity and latency can be achieved also when the broadcast source is mobile This study intendedly ignores the burden related to the selection of broadcast relay nodes within the mobile network and shows that optimal broadcasting in mobile networks is in principle possible We then investigate the broadcasting problem when the relay selection burden is taken into account and present a combined distributed leader election and broadcasting scheme achieving a broadcast capacity and latency which is within a Upthetalog n1+frac2alpha factor from optimal where n is the number of mobile nodes and α  2 is the path loss exponent However this result holds only under the assumption that the upper bound on node velocity converges to zero although with a very slow polylogarithmic rate as n grows to infinityLet us call the cells at cell distance i from the cell containing the source node the ith ripple We start showing that a for each cell A in the ith ripple the leader node of cell A transmits during round t + i the packet generated by the source node at round t The proof is by induction on i Property a trivially holds when i = 0 Assume now property a holds for each j  i In order for a to hold also for i we need to show that for any cell A in the ith ripple the node selected as leader for A during round t + i which is going to transmit during round t + i has received the packet generated by the source at round t before its transmission opportunity during round t + i Given that a is assumed to hold for j  i we have that the leader node of cell B where B is any of the cells in the i − 1th ripple adjacent to A note that at least one such cell always exists has transmitted during round t + i − 1 the packet generated by source node at round t Given the rules for selecting leader nodes we have that the leader node at round t + i − 1 for cell B is selected amongst the nodes located in the central minicell of B at the beginning of round t + i − 1 By Proposition 1 we have that at least one such node exists whp Furthermore the upper bound barv on node velocity guarantees that a node travels at most barv bark2 tau=fracl3 in the time elapsing between the beginning of round t + i − 1 and the beginning of round t + i Since the leader node of cell B was within the central minicell of cell B at the beginning at round t + i − 1 and given the above observation about the distance traveled by nodes we have that the leader node of cell B is still within cell B when it is scheduled for transmission during round t + i − 1 Hence by Proposition 3 we have that the packet transmitted by the leader node of cell B during round t + i − 1 which by induction is the packet generated by the source node at round t is correctly received by all nodes within cell A at the time of transmission In particular the leader node w for cell A at round t + i is within the central minicell of A at the beginning of round t + i which given the above observation about maximum traveled distance ensures that w was within cell A also during the entire round t + i − 1 Thus node w can correctly receive the packet sent by the leader node of cell B during round t + i − 1 and can forward it in the network when scheduled for transmission at round t + i which implies property aAssume the source s is somewhere south of the diagrams and the propagation front of packet p moves northward Stars represents cell leaders active in a certain round and the checkered region is the region covered by them The white area has not yet been covered by packet p while the gray area represents cells in Covp during a certain round On the left a circle represents a node lying in the white area which has not yet received p at a certain round t + j − 1 To avoid reception of packet p the node must cut the propagation front and reach the gray area during round t + j right where p is no longer transmitted Thus the node should travel distance at least 2l between the two consecutive roundsLet us consider now the interference experienced by u under the condition that in each cell with the same color there are at most m nodes Assume wlog that cellu has coordinates 00 Given the coloring scheme interferers lie in the cells with bottom left corner at xcdot kcdot lycdot kcdot l with xyinmathbfZ and x y ≠ 0 0 shaded cells in Fig 2Let P s denote a minimumhop cell path connecting cell Cs i with C c In other words P s is a minimumlength sequence of cells Csi=C 0dotsC j = C c such that for each q=0dotsj1 cells C q and C q+1 are adjacent We will prove that the packet generated by s at round i is propagated through P s till it reaches C c  with the packet progressing one cell at each round The proof is by induction on the cell distance q from Cs i More specifically we want to prove the following property a packet p i is correctly received by node LC q+1i + q during round i + q for any 0 ≤ q ≤ j − 1 Property a implies the lemma by observing that dCs i C c  = ds i implies existence of a cell path of length ds i connecting cells Cs i and C c To prove the base case q = 0 we observe that Lemma 8 ensures that p i is correctly received by all nodes that are located in cells adjacent to Cs i—including cell C 1—at time t i  + 2k 2τ On the other hand Lemma 7 ensures that node LC 1i remains within cell C 1 during the whole duration of rounds i and i + 1 Thus node LC 1i is guaranteed to be in cell C 1 at time t i  + 2k 2τ and to correctly receive p i Assume now that property a holds for any qprimeq By induction hypothesis node LC q i + q − 1 has correctly received p i at the end of round i + q − 1 We have to prove that p i will be transmitted by node LC q i + q − 1 during the next broadcast round i + q We first observe that in order for a packet to be transmitted by a nonsource node the packet had to be stored in the transmit buffer upon reception This happens if and only if the following three conditions are fulfilled 1 the node is the leader of its cell for the current round 2 the cellID in the packet equals the cell to which the node belongs and 3 packet ID is larger than that of the last received packet It is easy to see that condition 1 is fulfilled at node LC q i + q − 1 Condition 2 is fulfilled under the assumption which holds without loss of generality that the next cell selected by node LC q−1i + q − 2 when transmitting p i was set to C q As for condition 3 we have to prove that packet ordering is preserved when forwarding packets generated by the source towards cell C c More specifically we have to prove that packets p j with j  i cannot be received by LC q i + q − 1 before packet p i Note that there are two possible ways in which a packet p j with j  i can be propagated “faster” than packet p i —i packet p j is a new packet generated by s and s has moved along P s in the direction of C c and—ii packet p j is a packet relayed by a leader node on its route to cell C c As for case i we observe that by Lemma 6 node s can only move to adjacent cells during a broadcast round hence its speed cannot exceed the speed of packet p i propagation towards C c Yet it is possible that say node s is located in cell C 1 at round i + 1 possibly leading to impaired packet ordering in case packet p i+1 is transmitted by s before packet p i is forwarded to C 2 by node LC 1i However the transmission slot reserved for source transmission is located after the 2k 2 slots allocated for forwarding pending packets to the center cell C c  hence packet ordering is preserved in case i As for case ii we observe that it is possible for a leader node to have two packets in the transmit buffer during a certain round due to eg mobility of the source in the direction of the center cell as explained above However in case multiple packets are present in the transmit buffer older packets are prioritized over newer ones thus preserving packet ordering also in this case We have then proved that packet p i is stored in the buffer of node LC q i + q − 1 during round i + q − 1 We now have to prove that node LC q i + q − 1 will transmit this packet during round i + q and that node LC q+1i + q correctly receives the packet As for the first part observe that nodes in cell C q have two transmission opportunities during round i + q since node LC q i + q − 1 has at most two packets in its transmit buffer packet p i  and possibly packet p j with j = i − 1 or j = i + 1 two transmission opportunities are sufficient for node LC q i + q − 1 to transmit all packets in the buffer including packet p i To see why at most two packets can be stored in a node’s transmit buffer it is sufficient to observe that multiple packets are sent by a cell only when the source is traveling say from cell C k to cell C k+1 in a round j in which case two packets will be transmitted by cell C k+1 during round j + 1 the packet p j sent by the source at round j and the new packet p j+1 generated by the source at round j + 1 If the source would be allowed to move to cell C k+2 during round j + 2 we would have cell C k+2 transmitting 3 packets at round j + 2 packets p j   p j+1 and the new packet p j+2 generated by the source at round j + 2 However Lemma 6 implies that the source cannot move to cell C k+2 during round j + 2 since it can cross at most one cell during the duration of two broadcast rounds This implies that every cell transmits at most two packets during any centercast phase of the broadcast round which in turns implies that at most two packets can be stored in a node’s transmit bufferWe are now left to show that node LC q+1i + q correctly receives packet p i By induction hypothesis by the fact that leader nodes are unique in a cell and by Lemma 7 we have that the only node in cell C q that has nonempty transmit buffer during round i + q is LC q  i + q − 1 implying that there is no conflicting transmission from other nodes in C q during node LC q i + q − 1 transmissions In order to prove that node LC q+1i + q correctly receives p i  it is sufficient to observe that by Lemma 7 node LC q i + q − 1 is still within cell C q during round i + q which implies that packets sent by this node during round i + q are correctly received by all nodes in adjacent cells including node LC q+1i + q square

Keywords: