November, 2006IEEE P802.15-15-06-0479-00-0005
IEEE P802.15
Wireless Personal Area Networks
Project / IEEE P802.15 Working Group for Wireless Personal Area Networks (WPANs)Title / Timer-based Reliable Broadcast for WPAN Mesh Networks
Date Submitted / [November 4, 2006]
Source / [Inhwan Lee (1), Sungrae Cho (2), Bong Soo Kim (1), and Cheol Sig Pyo (1)]
[(1) ETRI, (2) School of Computer Science and Engineering, Chung-Ang University]
[221 Heukseok, Dongjak, Seoul 156-756, Republic of Korea] / Voice:[+82-2-820-5766]
Fax:[+82-2-820-5766]
E-mail:[
Re: / IEEE P802.15.5 WPAN MESH Networking Call for Additional Contributions dated on July, 2006 in IEEE P802.15-06-0333-04-0005
Abstract / [Reliable broadcast intrinsically causes the well-known problem of feedback implosion. The feedback implosion also causes collisions and thus significant power consumption in WPAN mesh networks. In this document, an energy-efficient reliable broadcast called Timer-based Reliable Broadcast (TRB) is proposed.]
Purpose / [To reduce the power consumption in reliable broadcast for WPAN mesh network]
Notice / This document has been prepared to assist the IEEE P802.15. It is offered as a basis for discussion and is not binding on the contributing individual(s) or organization(s). The material in this document is subject to change in form and content after further study. The contributor(s) reserve(s) the right to add, amend or withdraw material contained herein.
Release / The contributor acknowledges and accepts that this contribution becomes the property of IEEE and may be made publicly available by P802.15.
1. Introduction
Reliable broadcast is a useful service in WPAN mesh networks, such as reliable software updates, query dissemination, etc. For instance, software update at each node in WPAN has to be ensured by retransmission (or rebroadcast) triggered by feedbacks (i.e., ACK or NAK) from receiver nodes.
However, reliable broadcast intrinsically entails the well-known problem of feedback implosion since it is possible that every receiver node sends their feedback simultaneously to their transmitter as shown in Figure 1. This problem is exacerbated as the number of receiver nodes increases. In the domain of WPAN mesh network, this problem results in more contention, collisions, and thus more power consumption.
Figure 1– Feedback Implosion Problem.
If we have a scheme to limit the number of feedbacks, it is expected to significantly reduce the unnecessary power consumption. In this document, a new reliable broadcast scheme referred to as timer-based reliable broadcast is proposed by aiming two objectives:
Reliability
Lower Power Consumption
The basic idea is that receiver nodes intentionally delay their feedback (ACK or NAK) by a random time. If the first node[1] sending its feedback informs of its transmission to other nodes, the other nodes can suppress their feedback. By this way, we will achieve significant energy savings especially in multi-hop WPAN mesh networks.
2. Timer-based Reliable Broadcast (TRB)
The proposed timer-based reliable broadcast (TRB) exploits a random timer in a range of [0, D] at each node when each node needs to send its feedback. Since the feedback can be lost due to error or collision, the transmitter also employs a timer D.
In the proposed TRB scheme, transmitter performs the following procedure repeatedly without any order:
- When it has broadcast data,
UPSTREAM: If the data is from its child, it does the following in its appropriate schedule:
It broadcasts the data (piggybacked by ACK/NAK) to its children (not to its siblings), and sets its timer D.
It unicasts the data to its parent and its associated neighbors, and sets its timer D.
DOWNSTREAM: If the data is from its parent
It broadcasts its data to its children (not to its siblings) and associated neighbors, and sets its timer D.
THE OTHER CASES: If the transmitter is the originator of the data, it does the following in its appropriate schedule:
It broadcasts the data to its children (not to its siblings), and sets its timer D.
It unicasts the data to its parent and associated neighbors, and sets its timer D.
In all cases, a node that received a broadcast data from other node does not unicast back to that other node.
If timer D expires before receiving feedback (ACK/NAK), it retransmits the original data as above.
- After receiving feedback,
Once the transmitter receives a NAK, it retransmits its data as described in item 1 to fix the error, and sets its timer D.
When an ACK received, the transmitter transmits its next broadcast data as described in item 1, and sets its timer D.
The receiver performs the following procedure repeatedly without any order:
- After receiving broadcast data,
When a node receives a broadcast data, it delays its acknowledgement by a random timer described below:
If the received data is erroneous, the node activates a NAK timer.
If the received data is OK, the node activates an ACK timer.
If its timer expires, the node responds (with unicast) its feedback (NAK or ACK) to its transmitter.
NAK timer is generated at random in range of [0, αD] while ACK timer is generated at random in range of [αD, D] as shown in Figure 2.
Shorter timer for NAK causes early rebroadcast of the original data to fix errors.
Longer timer for ACK is for the case that all nodes successfully received the data.
Figure 2: Timer Setup at Each Receiver Node.
- After receiving rebroadcast data,
The receiver node cancels its timer (NAK or ACK).
This will reduce unnecessary feedbacks to the transmitter.
Based on the result of error detection/correction, the receiver uses NAK/ACK timer.
This series of procedure will continue up to predefined number of times.Overall behavior will look like as in Figure 3 for an example.
Figure 3– Overall Behavior (Example).
First, the transmitter broadcasts its data. Upon receiving it, the first and following[2] NAKs are transmitted back to the transmitter from receivers. Due to the first NAK, the transmitter rebroadcasts the data. Then, the other nodes suppress their timer (either NAK or ACK) if their timer is after reception of the rebroadcast data. Suppose that one error is detected at one receiver. Then the receiver sends its NAK. Upon reception of the NAK, the transmitter rebroadcast its data. Finally, all receivers do not have any error. One of the receivers sends its ACK make the transmitter initiate the next broadcast data.
SubmissionPage 1
[1]It is possible that its sibling node is not in its communication distance, there should be a small modification. In other words, informing its transmission is done by the transmitter. In this case, the transmitter should send its rebroadcast data if the feedback is NAK or send next data if it is ACK.
[2]Some of the NAKs are not suppressed if they are scheduled to expire before reception of the rebroadcast data.