Distributed Time Division Piconet Coexistence Using Local Time Offset Exchange
로컬 오프셋을 이용한 분산 시간 분리 피코넷 충돌회피 방법론
- Publish: Journal of the Korea Institute of Information and Communication Engineering Volume 18, Issue6, p1447~1453, 30 June 2014
Wireless Body Area Networks (WBAN), standardized as IEEE 802.15.6, enable digital devices on/around the human body to communicate with one another. WBAN is essentially a person's piconet consisting of a master (mobile) device and several slave devices, which follows his/her mobility pattern, and hence, occasionally collides with another piconet as people meet or pass by. As such, a mechanism to detect collision and avoid interference is needed for intra-piconet communications. In this paper, we focus on this notorious problem of piconet collision and propose Distributed Time Division Piconet Coexistence (DTDPC) using local time offset exchange as a simple, attractive solution. The proposed DTDPC provides different level of services for various applications. Besides our simulation results have shown that the proposed solution outperforms the conventional CSMA protocols.
IEEE 802.15.6 표준인 무선 Body Area Networks (WBAN) 은 여러 디지털 장비들을 가지고 있는 사람과 사람간의 통신규약이다. WBAN 에서는 하나의 주 디바이스와 여러 개의 부 디바이스들을 가진 한 사람 단위로 피코넷이 구성 되며, 이 피코넷은 사람의 움직임에 따라 이동하게 되며, 다른 사람과 근처에 있게 되면 피코넷간의 충돌이 일어나게 된다. 따라서 이와 같은 충돌을 감지하고 간섭을 회피하는 일이 피코넷 내부 통신을 위하여 필요하게 된다. 이 논문에서는 피코넷 충돌에 관하여 논하며, 간단하며 유용한 로컬 오프셋을 이용한 분산시간 분리 피코넷 충돌회피 방법을 제시한다. 이 제시된 방법은 여러 응용(동영상, 보안, 의료 등)을 위하여 응용마다 다른 수준의 서비스를 제공하는 하게 되는 기능을 갖게 되며, 수행된 실험 결과는 전통적인 CSMA 에 비교하여 성능이 뒤지지 않음을 보인다.
WBAN , Piconet , Coexistence , Time Division , TDMA , CSMA
Nowadays, user-centric services over wireless links is drawing public attention as a promising technological trend. As such, the need for networking among small devices or sensors on the body is rapidly increasing in areas like e-healthcare or wearable entertainments. One good example is a mobile device called personal information goggles to realize the high data-rate streaming or augmented reality service.
To address this need, Wireless Body Area Networks (WBAN) have recently been introduced. WBAN is designed for person-to-person or person-to-machine communications and forms a piconet among a coordinator device and several small devices or sensors on or around the human body. So, the communication range of WBAN is limited to about 2 meters, and power emission of the system should be in compliance with the regulation for the human body.
IEEE standardization in 802.15.6 TG (Task Group) BAN  is defined for the specification of, for example, mobile phone-based WBAN to meet various requirements like low-power consumption, QoS, coexistence, etc. Among these requirements, the most critical one is the
piconet coexistenceto avoid the notorious problem of collision and interference among piconets in the densely populated area.
The piconet coexistence is challenging because conventional mechanisms, e.g., contention-free multiple access based on TDMA or time reference synchronization cannot support collision avoidance because the coordination among distributed and dynamic piconets is extremely difficult when there are many piconets in a small area. Although random frequency hopping sequence used in Bluetooth [2-5] may mitigate interference among piconets with no communication overhead, it results in low bandwidth utilization since the packet collision rate between difference hopping sequences increases with the number of hopping sequences. Motivated by these limitations, we propose a novel coexistence solution, called a
Distributed Time Division Piconet Coexistence(DTDPC) mechanism using local time offset exchange. DTDPC takes a distributed approach that effectively removes the requirement of a unified time reference, while allowing each node to maintain the time-offset of each of its neighbor nodes. The key benefit of DTDPC is its capability to provide exclusive time slots to the piconets within the interference range of each other at minimal bandwidth waste and as a result different level of services are provided for various applications. The evaluation results have shown superior performance of DTDPC compared to the conventional CSMA. The rest of the paper is organized as follows. Section Ⅱ presents the details of DTDPC. Section Ⅲ describes the simulation results, while Section Ⅳ summarizes the related work. Finally, the paper concludes with Section Ⅴ.
The multi-piconet coexistence problem is one of the major issues in WBAN. Within a piconet, member nodes normally communicate among themselves under the coordination of a master node. However, the problem arises if multiple piconets are operating within the interference range of one another, because piconets share the communication channel. Thus, for multiple piconets to operate without collision/interference, a sort of (distributed/centralized) coordination mechanism should be incorporated into the design of piconets.
The typical distributed coordination mechanism is Carrier Sense Multiple Access (CSMA). CSMA effectively deals with random and delay-insensitive traffic and works well with dynamically changing topologies. However, the drawback of CSMA is its unbounded delay and low channel utilization in regular traffic such as constant bit rate (CBR) streams.
Time Division Multiple Access (TDMA), on the other hand, is a centralized coordination mechanism. TDMA shows good performance in regular and delaysensitive traffic and enables simple implementation without the support of dedicated hardware. But unfortunately, the applicability of TDMA is quite limited in WBAN because it requires one central node to provide time synchronization reference and coordination. Since typical WBAN scenario involves many moving piconets, the existence of one central node (elected as a global coordinator) cannot be guaranteed as the central node can move away from the group of piconets or two piconet groups each with its own central node may meet together. Figure 1 illustrates what happens in the centralized TDMA when there are two groups of piconets, each separately synchronized and harmonized. As these groups get closer, the harmonization is broken due to the lack of synchronization between them. For the two groups to be harmonized again, some of the colliding nodes should reschedule their time slots after establishing a unified time reference between the groups.
The problem is that the time reference unification is difficult when there’s a large number (>100) of nodes within the interference region, as illustrated in Figure 2. For instance, communications between two reference nodes (to elect a winner) become very complicated if they are multiple hops away. Moreover, all the nodes in either of the two groups should change their time schedule according to the changed reference. The problem aggravates when the time reference node leaves the group because the member nodes should detect the disappearance of the reference node and elect a new one, both of which require excessive overhead and delay.
To cure the drawbacks of centralized TDMA, we take a distributed approach to sharing time-slots among piconets, and propose a DTDPC mechanism, in which a master node reserves its time slots and exchanges the time reservation information with other master nodes in the distributed manner. Clearly, it is enough to solely consider the master node of each piconet in DTDPC, because a global coordination is performed among master nodes while the medium access information is simply fed to the slave nodes. Thus, we refer to the master node as just a ‘node’ throughout the rest of the paper.
DTDPC effectively removes the necessity for a unified time reference by allowing each node to maintain the time-offset of each of its neighbor nodes. To this, each node (1) broadcasts a time-schedule advertisement, and (2) translates, upon reception of the advertisement from its neighbors, the advertised time into its local time. This means DTDCP has no specific reference node, and instead, every node maintains the time offset with respect to each of its neighbors. In other words, each node is synchronized to each of its neighbors. With this approach, the time reference and the schedule information can be maintained in a completely distributed/localized manner.
Note that the time-offset value between two nodes can be calculated using any of the time synchronization algorithms  which means DTDPC is independent of the choice of synchronization algorithm. The accuracy of the time-offset value and the efficiency of the offset derivation entirely depend on the underlying synchronization algorithm.
We now describe how we realized the piconet coexistence mechanism in a distributed manner. In Fig. 3, T1, T2, and T3 are the time-offsets of node pairs, A-B, A-C and B-C, respectively. For example, the super-frame of node B starts T1 [sec] later than that of node A. Besides, STX and DX respectively represent the starting time and the duration of the time-slot reserved by node X (where X = A, B or C).
We define a schedule table, called Distributed Time Division Schedule Table (DTDST), for a node to maintain the information on the reserved time-slots (e.g., see the three tables in the middle of Fig. 3). DTDST has the following fields: Addr, # hop, Offset, Slot-Start, Slot-Dur, and Seqno. The Addr field encodes the address of the reserving node, while the #hop and Offset fields represent the hop-distance and the time-offset between the table owner and the reserving node, respectively. The Slot-Start field gives the starting time of the slot in terms of the local time of the table owner, and the Slot-Dur field the duration of the slot. The Seqno (sequence number) field indicates the freshness of the received information.
DTDST is periodically advertised through the schedule advertisement message at the bottom of Fig. 3. The Offset field is not included in the schedule advertisement message. Upon receiving the schedule message, a node copies Addr, Slot-Dur and Seqno fields from the message into its DTDST. Next, the # hop field is calculated using the distance vector routing algorithm as follows: a node add 1 to the hop-distance specified by the received schedule message and sets its corresponding hop-distance with this value. It discards the schedule information if the hop-distance field is larger than a predefined range, implying the sender is outside the interference range. The slot start time can be derived from the Slot-Start field in the received schedule message by adjusting it using the Offset value from DTDST. Let’s consider the following example. The slot start time of node A is STA by its local clock. This value is advertised to nodes B and C. Then, the offset value of node B with respect to node A is –T1, which means node B’s time lags behind node A’s time by T1. Thus STA by node A’s clock means STA –T1 by node B’s clock. Similarly, node C can calculate node A’s slot start time with respect to its local time.
An example procedure to build the tables shown in Fig. 3 is as follows. Note there is no scheduled slot at the beginning.
1. One of the nodes, say node A, schedules its time slot as required. Since there is no reserved time slot, node A can freely select its time slot.
2. Node A advertises this schedule information to the other nodes. Nodes B and C thus receive and record the schedule information in their DTDSTs.
3. Later, node B reserves its slot and advertises the corresponding schedule information, so that nodes A and C record this information in their DTDSTs. Node B chooses its slot start time such that its slot does not overlap with node A’s slot.
4. Finally, node C executes the same procedure as node B did to build DTDSTs shown in Fig. 3
We discuss the exception handling capabilities of DTDPC. It is possible that two or more nodes happen to have overlapping time slots even though they are within the mutual interference range. This can happen (1) if the nodes execute their time-slot reservation almost simultaneously (within a short period) so that later nodes select their slots before receiving the information from the earlier node, or (2) if a node with overlapping slots gets into the mutual interference region. DTDPC can resolve these collision events after the colliding nodes receive the schedule message including slot information from the other colliding nodes. Basically schedule messages in DTDPC are transmitted using CSMA, in which a new packet keeps on retransmission if there is any ongoing packet on the channel, thus schedule messages will eventually be delivered even when there is a slot collision. We may further enforce the nodes to randomly delay the schedule message broadcasting.
When a node has reserved slots, it can use them exclusively (i.e., with no collision/interference) within its piconet. Thus any type of channel access mechanisms including CSMA, centrally controlled TDMA, polling, etc. can be used for intra-piconet communications. By contrast, unreserved time slots can be freely accessed using CSMA for intra- or interpiconet communications. Schedule messages in DTDPC are also transmitted in these time intervals.
Packets in the unreserved intervals should not intrude into any reserved time intervals. To guarantee this requirement, a node should check if the packet can overlap with any reserved time interval before transmitting a packet, and if so, defers the packet transmission until the next unreserved interval. With this mechanism, all inter- and intra-piconet packets can be transmitted without collision provided that each node has all the schedule information of the nodes within its interference range.
If some nodes fail to get all the required schedule information, CSMA packets can collide with TDMA packets. That is, if a CSMA packet is ongoing, a TDMA packet may start to be transmitted regardless of the ongoing packet. Returning to the case when two distant nodes come close or two nodes happen to reserve overlapping time intervals, continuing schedule packets from one node may collide with TDMA packets from the other node. Nevertheless, the schedule packets will eventually be transmitted successfully because the transmission time will continue to change randomly according to a random backoff algorithm of CSMA. Once the schedule message is received, time slot collision can be resolved by changing the schedules of the colliding slots.
To evaluate the performance of DTDPC, we built our own simulator (in C) with the following settings. Piconets were located in the 6´6 [m] square area and the number of piconets were varied from 1 to 5. Maximum available system throughput was set to 10000[kbps] and the number of sensor nodes per piconet to 10. We implemented and used ‘Chaotic UWB (Ultra-WideBand)’  as the underlying physical layer, which is one of the candidates for WBAN standardization.
Figs. 4, 5 and 6 plot the performance of TDMA, CSMA and DTDPC in terms of the throughput, the packet error rate (PER) and the delay, respectively, under heavy traffic load situations that allow per-link (from the coordinator to the sensor node) throughput up to 10,000 [kbps]. The results can be analyzed as follows. First, TDMA was the worst performer and its performance got poorer as the number of piconets grew, with the exception that its throughput was the best when there were only a few (1 or 2) piconets. Second, DTDPC showed higher throughput and lower PER/delay than CSMA when heavy traffic loads were offered, meaning DTDPC outperforms CSMA as well as TDMA.
Besides the best performance of DTDPC at heavy-load situations, we found DTDPC achieved notable improvements when light traffic loads were offered (i.e., the maximum throughput was limited to 2000 [kbps] per link). That is, similarly to the heavy-load case, DTDPC showed the best performance and its delay was much lower than that of CSMA when the number of piconets was 4 or 5. Although CSMA is generally known to be the best solution when the system had light traffic loads, the CSMA mechanism inherently incurs delay to resolve collisions if piconets are not synchronized. By contrast, DTDPC had better delay performance than CSMA thanks to its use of time-offset exchange to suppress collisions. Finally, because collisions can still occur even if the offered load was low, the throughput-, PER- and delayperformance of TDMA got poorer as the number of piconets increased.
WBAN shall support a number of medical and multimedia applications [8-11]. The WBAN applications such as goggles for augmented reality and camcorders typically require high data rates, as opposed to the Bluetooth applications that do not require high data rates. The coexistence avoidance protocols for Bluetooth [2-5] are based on multi-hopping, in which nodes perform channel hopping at the event of collision, and hence, cannot support high data rate services. By contrast, the proposed DTDPC is tailored to the WBAN piconets, meeting their bandwidth requirements offering desirable features such as maximal bandwidth efficiency, dynamic allocation, and bounded-delay. Most importantly, DTDPC supports multiple piconets for high data-rate services through the distributed time-offset exchange.
In this paper, we have presented a piconet coexistence solution called Distributed Time Division Piconet Coexistence (DTDPC) that removes interferences or collisions among piconets in a simple, distributed manner, i.e., by having them to exchange the time-offset and schedule information. DTDPC has achieved many desirable features such as bandwidth efficiency, dynamic allocation, and bounded delay, and hence, can support different level of services to various services. For example, it can let multiple piconets run high data rate services and a piconet send high priority traffic in timely manner because it is capable to manage TDMA and CSAM and it is very important to provide and manage different level services for various applications in WBAN [12,13]. Also, our evaluation results have shown the best performance of DTDPC compared to TDMA and CSMA.
[그림 1.] 시간 참조를 통한 통합
[그림 2.] 중앙 집중 방식의 확장성 문제
[그림 3.] 분산적 시간 분할 방법
[그림 4.] throughput 성능 비교 (많은 traffic 경우)
[그림 5.] PER 성능 비교 (많은 traffic 경우)
[그림 6.] delay 성능 비교 (많은 traffic 경우)