Abstract
The scarcest resource for most of the wireless sensor networks (WSNs) is energy and the major factor in energy consumption for WSNs is communication. Not only transmission, but also reception is the source of energy consumption. The lore to decrease energy consumption is to turn off the radio circuit when it is not needed. This is why TDMA is advantageous over contention based methods. A time slot assignment algorithm is an essential part of TDMA based systems. Although centralized time slot assignment protocols are preferred in many WSNs, a centralized approach is not scalable. In this article, a new energy efficient, delay sensitive, and fault tolerant distributed time slot assignment algorithm, referred to as ft_DTSM, is proposed for sensor networks under convergecast traffic pattern. ft_DTSM aims at operating with low delay and low energy under faulty nodes assumption. Instead of random access based periods, it assigns slots with the help of tiny request slots. While traditional slot assignment algorithms do not allow assigning the same slot within two hop neighbors, because of the hidden node problem, ft_DTSM can assign, if the assignment is suitable for convergecast traffic. Simulation results have shown that both delay and energy consumption performances of ft_DTSM is superior to existing distributed slot assignment protocols for WSNs. ft_DTSM can also distribute the slots so that the network can continue its operation against a single point of failure. Although ft_DTSM has a somewhat longer execution time, its scalability characteristic may provide application specific time durations.
Introduction
Developments in micro-electro-mechanical systems (MEMS) technology have enabled to integrate battery-operated sensor, computational power, and wireless communication components into a small size, low-cost device [1, 2]. These tiny sensor nodes, which consist of sensing, data processing, and communication components, leverage the idea of wireless sensor networks (WSN) based on the collaborative effort of a large number of nodes [3]. While the sensor nodes can be deployed on the terrain, in some cases, they can be deployed under the sea [4] or even underground [5]. Although, in most cases, WSNs measure scalar physical phenomena like temperature and pressure, it can also be used to capture multimedia data as in Wireless Multimedia Sensor Networks (WMSNs) [6]. Military and civilian applications include but are not limited to intrusion detection, information gathering, inventory tracking, and environmental monitoring [7].
Wireless sensor nodes generally carry limited and irreplaceable power sources. Thus, energy efficiency is one of the most important factors in most of the WSN applications. A sensor node consumes energy for sensing, communication, and data processing where the dominant factor in energy consumption is communication [8]. The most common way to reduce energy consumption is to turn off the radio circuit when it is not needed. TDMA has a natural advantage over contention-based medium access methods [9]. In TDMA, nodes listen and send data with a certain schedule. Hence, at other times, nodes do not need to use the radio circuit, hence they can turn it off. One of the main problems of TDMA based systems is the time slot assignment. In this article, a new fault tolerant distributed time slot assignment mechanism (ft_DTSM) is proposed for TDMA based WSNs with convergecast traffic assumption. The most important design considerations of ft_DTSM are energy efficiency, delay, reliability, and scalability.
Distributed time slot assignment is not a new topic for wireless networks. DTSAP (Dynamic Distributed Time Slot Assignment Protocol) [10–12], FPRP (Five-Phase Reservation Protocol for Mobile Ad Hoc Networks) [13], E-TDMA (Evolutionary-TDMA Scheduling Protocol) [14], HRMA (Hop-Reservation Multiple Access) [15] are examples of distributed scheduling protocols for ad hoc networks. Most of the ad hoc network algorithms are developed for peer-to-peer data traffic. However, data traffic in WSNs is mostly from sensor nodes to the sink or simply convergecast. Existing slot assignment algorithms for ad hoc networks cannot satisfy energy and delay requirements of WSNs under convergecast traffic, which is why they cannot be directly applied. Consequently, WSNs need a delay-sensitive and energy-efficient slot assignment algorithm under convergecast data traffic.
There is a lot of research about distributed time slot assignment for sensor networks. Patro et al. have proposed Neighbor Based TDMA Slot Assignment Algorithm for WSN [16]. A mobile agent visits every node and assigns a proper slot. This method reduces the required number of slots and increases channel utilization. However, it is not energy efficient, since copying and running the agent consumes a high amount of energy. Kanzaki et al. have also proposed an adaptive slot assignment protocol for WSN [17]. Nevertheless, the main design objective is the channel bandwidth, not delay or energy efficiency. Another distributed slot assignment algorithm for sensor networks is presented in [18]. It reduces delay for broadcast, convergecast, and local gossip traffic patterns for different grid topologies. However, in many sensor network applications, sensor nodes are deployed randomly. In addition to this difficulty, it does not consider energy consumption; its design consideration is only to minimize delay. SMACS [19] uses a different distributed time scheduling algorithm. After a series of handshaking signals, neighbor nodes can agree on a frequency and time pair to construct a link. SMACS produces a scalable and reliable flat network. However, SMACS needs FDMA as well as TDMA, but sensor nodes are so tiny and limited that current sensor nodes cannot meet the requirements of SMACS. DRAND [20] is a randomized dining philosophers algorithm for TDMA scheduling of wireless sensor networks. This algorithm is the first distributed implementation of RAND [21], a commonly used, centralized channel assignment algorithm. Randomized dining philosophers approach is scalable and robust. However, in DRAND, before having a schedule, nodes communicate with each other using a contention based MAC protocol, and it increases energy consumption. In [22], another distributed slot assignment algorithm is proposed. It also uses CSMA/CA to schedule the slots and it consumes high energy during the slot assignment period, like DRAND [20]. μMAC has another slot assignment mechanism that includes a contention period [23]. Oriented Link Scheduling is also a distributed time slot assignment algorithm, but its main design considerations are the complexity of the algorithm and the number of used time slot minimization [35]. It does not deal with delay or fault tolerance. In [36], a new slot assignment algorithm is proposed to minimize energy consumption with the help of special control slots. However, it cannot reduce delay.
TRAMA [24] is a TDMA-based sensor network system and it includes a distributed slot assignment mechanism. It has a random access period to be able to assign proper slots, and its random access period is also contention based. In TRAMA, all the nodes have to listen to the medium in random access periods. It increases energy consumption of TRAMA. FLAMA [34] is another slot assignment algorithm that uses random access period, like TRAMA [24]. FLAMA adapts medium access schedules to the traffic flows exhibited by the application. With the help of application awareness, FLAMA achieves significantly smaller delays (up to 75 times) when compared to TRAMA, which results in significant improvement in energy savings and reliability. However, contention based structure of FLAMA still consumes considerable amount of energy. DTSM [30] is another distributed time slot assignment scheme for wireless sensor networks. It uses tiny time slots like FPRP [13]. DTSM distributes the slots based on hop numbers of the nodes. In this way, it achieves significant delay reduction. However, it is very vulnerable to single point of failure. Because of high failure rates of sensor nodes, it is a significant handicap.
In this article, a new delay-sensitive, energy-efficient, fault-tolerant distributed time slot assignment algorithm, ft_DTSM, is proposed for wireless sensor networks. The design considerations of ft_DTSM are delay, energy consumption, reliability, and scalability. There are a number of advantages of ft_DTSM design over the existing designs. First, unlike existing slot assignment protocols that includes 802.11 like contention sessions, nodes in ft_DTSM contend in time slots, like FPRP [13]. In 802.11 [29] like random access based sessions, all nodes must listen to the medium and keep their radio circuits open during the contention based session. This strategy consumes a high amount of energy. Contention in tiny time slots results in lower energy consumption. Another important feature of ft_DTSM is its convergecast traffic aware design. Most of the time, wireless sensor networks use convergecast traffic pattern. In convergecast traffic, data relays from the nodes into the sink. ft_DTSM assumes that nodes always forward data to their neighbors that are with a lower hop number. In order to decrease delay, ft_DTSM assigns the slots on the basis of the hop number of the nodes. Unlike existing slot assignment algorithms, ft_DTSM allows the assignment of the same slots to the nodes within a two-hop region, if the assignment allows convergecast traffic. Another advantage of ft_DTSM is its reliable structure. It can distribute the slots so that the sensor network can recover itself against single point of failures.
The rest of this article is organized as follows. In Section 2, details of the existing time slot assignment algorithms for WSN are discussed. In Section 3, basic assumptions and the system design of the proposed algorithm is introduced. In Section 4, performance results and discussion are presented. Finally, the conclusion is given in Section 5.
Related Work
Instead of distributed algorithms, many TDMA based MAC protocols for sensor networks prefer to assign time slots centrally [25]. Especially, sensor networks based on small clusters prefer a centralized approach as in [26–28]. Sensor nodes connect to the nearest cluster head. The cluster head collects data about the nodes in its cluster and creates a schedule centrally. The cluster head broadcasts this schedule to its nodes. However, this approach has disadvantages. Data about sensor nodes must be forwarded to the cluster head with a contention based system like 802.11 which increases energy consumption. Inter-cluster interference is another problem of these sensor networks. In most of the cases, interference is handled with the CDMA approach, which requires considerable computation power. Even if these disadvantages can be handled, not all sensor networks are cluster based and there is no easy way to implement central time slot assignment for wireless sensor networks that are not cluster based.
Most of the existing slot assignment algorithms for sensor networks are based on 802.11 like contention periods. SMACS [19], DRAND [20], TRAMA [21], FLAMA [34] can be classified as this kind. They have a random access period. Slot request and slot grant data exchange is performed in this period. In this article, FLAMA [34] is presented as an example. Time slot organization of FLAMA is presented in Fig. 1. It has two major components, scheduled access and random access.
Time slot organization of FLAMA.
The scheduled period is basically used for data transmission with no contention. However, during the random access period, nodes perform contention based channel acquisition and thus the signaling packets are prone to collisions. All the nodes have to listen to the medium in the random access period. Although FLAMA can save considerable amount of energy in its scheduled period, very serious energy waste still takes place in the random access period.
Another approach for distributed slot assignment is to use tiny time slots, instead of random access based periods. In this approach, all nodes are assumed to be synchronized. Nodes send their requests and grants in tiny slots. After a series of handshaking, if a node can receive the required signal successfully, it reserves the slot. Five-Phase Reservation Protocol, FPRP [13], is one of the most known examples of this class of distributed slot assignments. FPRP is a slot assignment protocol that uses a five-phase reservation handshaking process to establish TDMA slot assignments. It is fully distributed and can run parallel in the network. In other words, it is entirely insensitive to the network size. Unlike TRAMA or FLAMA, it does not need the support of additional MAC protocol like 802.11.
Overview and Assumptions
ft_DTSM is a new distributed time slot assignment protocol for wireless sensor networks.
It is developed to operate with low energy, low delay, and high reliability. Because of its
distributed nature, ft_DTSM can run in any network size without central node. It does not
need any additional MAC layer support. It has a new mechanism to reduce delay and to construct a
reliable topology, so it can be used in delay sensitive applications under single point of failure,
like military monitoring. Before explaining the details of ft_DTSM, assumptions are presented
as follows: Sensor nodes will be immobile. Radio channel is symmetric. Before running ft_DTSM, all nodes must synchronize their clock. There are many time
synchronization schemes for sensor networks [22, 28]. Data traffic is convergecast. Data traffic always flows from the sensor nodes to the sink. This
is one of the most common data traffic type for WSNs.
Description and Slot Organization of ft_DTSM
Instead of random access period like TRAMA [24], FLAMA [34], or DRAND [20], ft_DTSM uses time slots to exchange scheduling signals. The slot organization of ft_DTSM is presented in Fig. 2. The numbers of the reservation frame, the reservation slot, and the reservation cycles for each reservation slot are fixed parameters of ft_DTSM.
Slot organization of ft_DTSM
ft_DTSM assigns the slots in reservation frames. Every reservation frame begins with advertisement slots (AS). The number of tiny slots in AS is equal to the number of time slots that will be distributed. This way, there is one corresponding tiny slot for every time slot in AS. All the nodes with a valid slot send a special signal in the corresponding slot in AS. All the nodes that have no valid slot listen to all tiny slots in AS. If a node can receive a number of valid signals more than a certain number; i.e., the fault tolerance parameter, it means the reservation frame for its hop number is about to begin and it can compete for the slot assignment. Every reservation frame is used for the corresponding hop numbered nodes. According to this hop numbered structure, in the first reservation frame, the nodes with hop number one can get the slots. After that, the nodes with hop number two get the slots and so on.
Slot assignments for a specific hop number are performed in reservation slots. Each reservation slot corresponds to a specific available data transmission slot. In this case, the number of reservation slots and the number of available data transmission slots for a particular hop number are the same. There are a certain number of reservation cycles in each reservation slot. The number of reservation cycles for each reservation slot is constant and it is a parameter of ft_DTSM algorithm. There are four tiny slots in each reservation cycle and signal exchanges take place in these slots.
ft_DTSM is developed under the assumption of convergecast traffic. If data flow through the higher hop numbered nodes to lower hop numbered nodes, convergecast traffic can be realized. In ft_DTSM, a node with hop number h sends its data only to a node with hop number h-1.
The minimum condition for convergecast traffic is that for every node in hop number h, there must be at least one node in hop number h-1 that can receive its signal. This way, every node in hop number h can send its signal to a node in hop number h-1. DTSM [30] is designed to work for a minimum condition of convergecast traffic. However, if there is only one parent alternative for a set of nodes and if that parent node fails, some nodes cannot communicate. This is why having at least one parent alternative is the minimum condition.
Sensor nodes are prone to failures and a sensor network must be fault tolerant against failures. The minimum condition for convergecast traffic is not reliable under a single point of failure. If there is only one node that can receive the signal of a certain node and if the receiving node goes off, the sender cannot send its message. There should be more than one node that can receive the message of the sender. The solution for a reliable convergecast traffic network lies between the traditional network condition (no node within a two-hop neighborhood can get the same slot) and the minimum condition (having at least one parent alternative). The nodes in hop number h should get the slots so that a certain number of nodes in hop number h-1 can receive all the signals from h hop numbered nodes clearly. The number of h hop numbered nodes that can receive the signal of h-1 hop numbered nodes is defined as a fault tolerance parameter, ftp. A node can find at least ftp alternative parent nodes to send its message. This model increases the number of receiving nodes in hop number h-1 for the senders in hop number h and it results in a more fault tolerant network. Figure 3 shows the situation with a certain example.
Sample slot assignment.
In Fig. 3, nodes A and B are with hop number h, whereas node C, D, and E are with hop number h-1. If there is a connection between two nodes, they can hear each other. In traditional slot assignment algorithms, A and B cannot have the same slot. However, the minimum condition of convergecast traffic is satisfied. According to the minimum condition, there must be at least one node in h-1 hop number that can receive the signals of the nodes in h hop number. If A and B get the same slot, A can send its data to C and B can send its data to D. However, reliability may be a problem in this case. For example, if C fails, A cannot send its data or if D fails, B cannot send its data. According to ft_DTSM signal exchange structure, slots must be distributed so that for each h hop numbered node, there must be more than fault tolerance parameter nodes with h-1 hop number that can receive the signals of the nodes in h. In Fig. 3, if A and B get the same slot, E cannot receive the signals. ft_DTSM does not give the same slot to A and B. This way, if C or D fails, E can still receive the signals of A or B.
Although ft_DTSM is more constrained than the minimum condition of convergecast traffic, it is more relaxed than FPRP. In Fig. 3, even if E does not exist, A and B cannot get the same slot in FPRP, because of the connectivity between A and B. However, ft_DTSM can give the same slot to A and B, because ft_DTSM checks only the collision between h-1 hop numbered nodes and h numbered nodes.
Signal exchange is designed based on four tiny slots. These are the request slot, the collision report slot, the confirmation slot, and the acknowledgement slot. The diagram of slot assignment signal exchanges is illustrated in Fig. 4. In this scenario, A and B can hear each other and C can communicate only with A. The hop number of A and B is h, whereas the hop number of C is h-1.
A successful signal exchange scenario.
The first slot of a reservation cycle is the request slot. In this slot, every node that receives more than the ftp signal in the latest advertisement slots requests a slot with a certain probability.
Let us assume that the hop number of the node is h. For a valid request, it sends a signal in the request slot. Only the nodes with hop number h-1 may suffer from the collision of the requests. The nodes that are with the hop number h-1 listen to the request slot. If these nodes receive a jammed signal in this slot, it means there is a collision. The nodes that detect a collision in the request slot send a signal in the second slot, which is a collision report slot. If the node can get a clear signal in the request slot, it does not send any signal. The nodes in the hop number h listen to the second slot. If a node has sent a request and if it does not receive a collision report in the second slot, it can get a valid slot. In the third slot, which is the confirmation slot, if a node can get a valid slot, it sends a signal. The other nodes with hop number h and h-1 listen to the confirmation slot. If a node with hop number h-1 receives a signal in the third slot, it means there is a node that gets the current slot. If a node with hop number h receives a signal in the third slot, it can not give the current slot to another node. In this case, all the h hop numbered neighbors of h-1 hop numbered nodes that receive a confirmation signal in the third slot send an acknowledgment in the fourth slot. The receivers of the acknowledgment signal do not contend for the current slot anymore.
At the end of this signal exchange some nodes can get valid slots. The nodes that cannot have a valid slot try to get one in the next reservation cycles. Reservation cycles are repeated for a certain number of times in a reservation slot.
The following theorem proves the correctness of ft_DTSM signaling structure.
Theorem. ft_DTSM signaling structure ensures that no two nodes with hop number h+1 can take the same slot number, if both of them can be received by a node with hop number h.
Proof
Let us assume that A and B are the nodes with hop number h+1, and C is the node with hop number h, and C can receive signals from A and B. According to ft_DTSM signal structure, if A and B want to get a slot, they transmit the signal in the first tiny slot, in the request slot. C listens to the request slot. C can receive the signal from A and B, so it receives a jammed signal in the request slot. In the second slot, which is the collision report slot, C sends a signal. This way, it reports the existence of the collision. The nodes that request the slot, like A or B, listen to the second slot. Neither A nor B receive the signal of C in the second slot. In this case, A and B do not send any signal in the confirmation slot and do not get the slot. It shows that two nodes with hop number h+1 cannot get the same slotnumber, if there is a h hop numbered node that can receive A and B.
At the beginning of the signal exchange, every node can send a request signal with a certain probability. This probability is not constant. It must be equal to 1/N c , where N c is the number of contender nodes in a one-hop neighborhood. The number of contenders can be found out with packet exchange within the nodes in a two-hop neighborhood. However, the packet exchange consumes considerable energy. Instead of finding the exact number of contenders, ft_DTSM tries to forecast N c as realistically as possible. Although forecasting saves energy, it also has disadvantages. If N c is forecasted larger than it is, the contention probability will be lower than it should be and the slot assignment algorithm may take longer than needed. If N c is forecasted smaller than it is, the contention probability becomes larger than it should be and the collision probability increases. N c should be updated according to the result of the reservation cycle. If a neighbor node achieves to get a valid slot, the number of contenders decreases. If there is a collision, N c must be increased to decrease the contention probability. If nothing happens, in other words, if the reservation cycle is idle, N c should be decreased to increase the contention probability.
ft_DTSM slot request probability update strategy is similar to FPRP [13]. FPRP is also adopted from Rivest's Pseudo-Bayesian Broadcasting Algorithm [31], which is designed for the distributed single hop ALOHA broadcast network. According to ft_DTSM strategy, if a node cannot receive or send any signal in a reservation cycle, it is idle. In the idle state, N c is decreased by one. If a node sends a request in the first slot and if it gets a collision report in the second slot, it is a collision. For a collision situation, N c is increased by 1/(e-2). If a node sends a request and does not receive a collision report in the second slot, it is a success for itself. The node gets a valid slot and it does not contend anymore. If a node that does not send a request and receives a confirmation, it means there is success one hop away. In addition to N c , a new value must be calculated to update N c for the success state. This new value, N b , represents the number of the nodes that have no valid slot and cannot contend due to success within one hop. The assumption is that if there is success one hop away, a portion of its neighbors which are modeled as R 1 cannot contend. After success one hop away, N b must be increased by R 1 times N c , and N c must be recalculated as 1-R 1 times N c . If a node receives a signal in the fourth slot, it means there is success for a node which is not directly a neighbor but the success is in the neighbor of a node in hop number h-1. In other words, success is two hops away. In this case, N c and N b must be updated as in the one-hop away success case. However, in this case R2 value must be used. The complete structure of updating the slot request probability is presented in Fig. 5.
Pseudocode of ft_DTSM slot request probability updating procedure.
One of the most important design issues for wireless sensor networks is delay. If the application is delay sensitive, like military monitoring or surveillance as in [32], data latency can be very important. In a military monitoring system, the existence of the enemy should be reported with minimum delay. Reducing delay is possible by the help of assigning time slots carefully. The rule is that the smaller hop numbered nodes should get higher slot numbers. In order to realize rescheduling, the time frame is divided into u sub time frames. If the whole time frame has s slots, then a sub time frame has s/u slots. The slot number assigned to a node with hop number h must be in (u-((h-1) mod u))th sub time frame. This way, the slot numbers of consecutive hop numbered nodes belong to consecutive sub time frames. The sensor node can get the number of sub time frames, u, from the sink's synchronization signal and calculate its sub frame number.
A sample network is presented in Fig. 6. Let us assume that the nodes in Fig. 6 are one hop away from its consecutives. In this particular network, the time frame has 30 time slots and there are 3 sub slots. In this case, the first sub slot is from 21 to 29th slots, the second is from 11 to 20th slots, and the third one is from 2 to 10th. The first slot is reserved for the sink.
Example network and time slots distributions (a) Random slot assignment. (b) ft_DTSM.
Figure 6a is an example of a slot assignment. Figure 6b is a slot assignment based on ft_DTSM. The relay of an event from C to the sink takes 70 time slots for a sensor network in Fig. 6a. However, it takes only 21 time slots for the rescheduled network in Fig. 6b.
Performance of ft_DTSM is discussed according to delay, energy consumption, running time, and fault tolerance. A simulator is implemented to compare ft_DTSM with FPRP, FLAMA, and DRAND. The sensor network is assumed to be composed of Berkeley's Motes [33]. Simulator parameters are presented in Table 1.
Simulation parameters
Simulation parameters
Another parameter for the simulations is the number of reservation frames and the number of reservation cycles in each reservation frame. Number of reservation frames and reservation cycles should be set so that all sensor nodes can have a valid slot with high probability and it should minimize energy consumption as well as run time. In order to find the optimum parameters, the existence of a central coordinator is assumed for FPRP and ft_DTSM. The pseudo code of the central coordinator is as in Fig. 7.
Pseudocode of central coordinator.
Average number of reservation cycles and reservation frames distributed with the central coordinator are calculated after 20 runs and the calculated numbers are used as parameters. The most important factor that affects these parameters is node density. The number of reservation cycles and reservation frames is set for each node density. Simulation results have shown that the parameters that are calculated with this methodology can assign valid slots with more than %99.5 probability.
Sensor nodes are prone to failures and a sensor network should be able to operate against a single point of failures. If a sensor node dies, the other ones should be able to continue with little or no additional recovery procedure.
We have defined a new fault tolerance metric to compare fault tolerance of different systems. Fault tolerance is the percentage of continuing sensor nodes, after a certain percentage of randomly picked sensor nodes have died. For example, if only 80% of the remaining nodes can operate after 10% of the sensor nodes have died, its fault tolerance for 10% is 80.
If there are a limited number of alternative parents in the system for a certain node, and if all alternative parents die, the children cannot send the data and the children cannot function. If there are more alternative parents, the system becomes more fault tolerant. FPRP and DRAND distribute time slots according to the two-hop neighborhood rule. If a parent of a node goes off in FPRP or DRAND, it can connect to another neighbor. If a FPRP or DRAND node is connected to the network, its fault tolerance is %100. FLAMA creates a tree topology and there is no alternative parent mechanism. FLAMA node has only one parent, and if the parent node goes off, the child cannot continue to operate. Figure 8 shows the comparison of fault tolerance performance of ft_DTSM and a system with no fault tolerance mechanism like FLAMA.
Fault tolerance of different systems.
When the fault tolerance mechanism is not used as in FLAMA, faulty nodes affect the whole network. If %20 of the sensor nodes goes off in FLAMA, only 65% of the remaining nodes can continue to operate. The fault tolerance mechanism achieves to keep the network alive against single point of failures. When the fault tolerance parameter is higher, the system becomes more fault tolerant. If 50% of the sensor nodes are faulty, 50% of the remaining nodes can continue to operate, when the fault tolerance parameter, ftp, is 1. When ftp is 2, it increases to 93. If ftp is 3, the fault tolerance performance of ft_DTSM is 97%. The fault tolerance performance is the same as when ftp is 4. If the parameter is higher than 2, the additional contribution is very limited.
Delay is one of the most important problems especially for TDMA based sensor networks. ft_DTSM has a special mechanism to reduce delay. Delay performance of ft_DTSM is investigated in three ways. ft_DTSM has a sub frame structure to decrease delay. First, the impact of a sub frame structure is investigated. Second, the effect of the fault tolerance parameter on the delay performance is presented. Third, ft_DTSM is compared with FPRP [13], which is developed for ad hoc networks, and FLAMA [34], which is developed for WSNs to minimize energy consumption and delay, and DRAND [20]. A simulation model is developed for delay performance comparisons. In the simulation, one data transfer time frame is assumed as one second. If a packet is composed of 64 bits, and a node can send one packet in one data slot, one data slot takes 3.3 ms.
Sub Frame Structure Effect
The first experiment is set up to show the effect of the sub-frame structure. So, the fault tolerance parameter is accepted as 1 for all cases. In our simulation, sub time frames are 5, 10, 20, and 30. Delay is related to the distance between the event and the sink. In order to investigate the delay performance, a circular network area with a 40 unit diameter is divided into 10 regions. The first region is 2 units distant from the sink. The second is 4 units distant from the sink, and so on. 100 events are generated for each region and simulation is repeated for 20 times. Figure 9 shows average delay of ft_DTSM with different number of sub frames.
Delay performance of ft_DTSM with different sub time frame numbers.
ft_DTSM is successful to decrease delay with its sub frame structure. Especially, when the distance is longer and the sub frame number is high enough, the delay can be reduced. Although the sub frame number affects the delay performance, it is not always directly proportional to the sub frame number. The delay performance of ft_DTSM follows a step pattern related to the average hop number between the event and the sink. For example, the average hop number for the 5th region is 10, and delay of ft_DTSM-20 and ft_DTSM-10 is approximately the same. After the 5th region, while the delay of ft_DTSM-10 increases, the delay of ft_DTSM-20 still stays almost constant. The same structure can be found for ft_DTSM-5. This step pattern is closely related to the average hop number of the region and the number of sub frames. The average hop number of the 5th region is 10 and delay of ft_DTSM-10, ft_DTSM-20 and ft_DTSM-30 is very close for region 5. If the region number is higher than five, the average hop number exceeds 10 and the delay of ft_DTSM-10 starts to increase. While the delay of ft_DTSM-10 increases, the delay of ft_DTSM-20 and ft_DTSM-30 stays approximately constant. It shows that the sub frame number must be chosen according to the maximum hop number of the sensor network. If the sub time frame number is lower than the maximum hop number, the delay increases. If the sub time frame number exceeds the maximum hop number, the delay is not reduced any more, it stays the same.
Another factor that affects the delay performance of ft_DTSM is the fault tolerance parameter, ftp. When the fault tolerance parameter increases, the maximum hop number of the network also increases, and when the hop number is higher, the delay also increases. Delay performances of ft_DTSM with different fault tolerance parameters are shown in Fig. 10. The sub slot number is assigned as 30, which is enough to minimize delay for all cases.
The delay performance of ft_DTSM with different ftp.
When the fault tolerance parameter in ft_DTSM increases, the delay also increases. Delay increase of ft_DTSM stems from the increase in maximum hop numbers with higher fault tolerance parameter. If the distance from the event to the sink is 20 units, ft_DTSM delay is around 1800 ms. for ftp 1. However, if the fault tolerance parameter is 4, the delay is approximately 2500 ms. Maximum delay difference between ft_DTSM with ftp 1 and ftp 4 is about 1.4 times.
Delay performance of ft_DTSM is compared with FPRP [13], DRAND [20], and FLAMA [34]. In this comparison, TRAMA [24] is excluded, because FLAMA, which uses flow information of the application, produces lower delay than TRAMA. The fault tolerance parameter is set to 2 and the number of sub frames is 30. Figure 11 shows the delay performances of ft_DTSM, FPRP, DRAND, and FLAMA.
Delay performances of different time slot assignment mechanisms.
FPRP, which assigns the slots without the traffic flow direction information, produces higher delay than ft_DTSM, and FLAMA. DRAND, which is a distributed version of RAND, assigns the slots randomly. FPRP also assigns the slots without any prior information. The delay performance of DRAND is expected as the delay performance of FPRP.
Unlike the other existing time slot assignment mechanisms, FLAMA uses data flow information. FLAMA's flow aware structure achieves to reduce delay. Figure 11 shows that ft_DTSM can produce lower delay than FLAMA. When the distance is 20 units, the delay performance of FLAMA is around 5300 ms. Under the same conditions, the delay performance of ft_DTSM is around 1800 ms.
Sensor nodes have limited energy and when the power goes off, the sensor node cannot function. Energy is one of the most critical resources for sensor networks. Slot assignment mechanism of a sensor network must be the energy saver, like any other algorithm used in sensor networks. First, the effect of the fault tolerance parameter on the energy consumption performance of ft_DTSM is investigated. Afterwards, the energy consumption performance of ft_DTSM is compared with the existing WSN time slot assignment mechanisms.
In ft_DTSM, the number of neighbor nodes with a valid slot must be higher than a certain fault tolerance parameter, ftp. An ft_DTSM node has to wait until it can find more than ftp neighbor nodes with valid slots. In this case, the maximum hop number of the resulting network also increases. Each reservation frame corresponds to a specific hop number. When the maximum hop number increases, the number of used reservation frames also increases. More reservation frames mean more energy consumption. Energy consumption performances of ft_DTSM with different ftp values are presented in Fig. 12.
Energy consumption of ft_DTSM with different ftp.
Energy consumption of ft_DTSM increases with increasing ftp and node density. When the node density is lower, the energy consumption performance difference is higher. If the node density is higher, all the energy consumption performances between different ftp become very close.
The energy consumption performance of ft_DTSM is also compared with FLAMA, FPRP, and DRAND. FLAMA is based on two different kinds of periods. In time slot periods, data traffic is realized. In a contention based period, FLAMA distributes time slots. Slot assignment algorithm of FLAMA is run in random access based period and all nodes have to listen or transmit in this period, which takes considerable energy. DRAND also uses 802.11 like the signal exchange mechanism and it needs a very large amount of signaling. FPRP does not use any additional MAC layer for slot assignment. However, it is not optimized for energy consumption. ft_DTSM is a distributed slot assignment algorithm designed for minimizing energy consumption.
One of the most important parameters for energy consumption of ft_DTSM is the node density. The simulation results for different node densities are presented in Fig. 13 to compare the energy consumption of ft_DTSM with the fault tolerance parameter 2, FPRP, DRAND and FLAMA.
Energy consumption comparison of time slot assignment algorithms.
Energy consumptions of slot assignment mechanisms increase with the increasing node density. While energy consumption increases the structure of ft_DTSM and DRAND is polynomial, the energy consumption of FPRP and FLAMA increases linearly. It is clear that the time slot assignment protocols that include random access based periods like FLAMA or DRAND consume much more energy than the slot assignment protocol based on tiny time slots, like FPRP or ft_DTSM. FPRP consumes less energy than ft_DTSM, when the node density is lower. While the node density is higher, energy consumption of FPRP exceeds energy consumption of ft_DTSM.
ft_DTSM, FPRP, FLAMA, and DRAND are compared with respect to their running times. FPRP is a fully parallel and distributed algorithm. All the nodes can run the FPRP algorithm at the same time. The reservation process for a given node only involves nodes within a two-hop radius, and is thus a local process. No coordination is necessary with more distant nodes. By keeping the reservation process localized (and running simultaneously over the entire network), the FPRP becomes insensitive to the network size. Its running time is constant. However, nodes run ft_DTSM according to their hop numbers. It follows a wave pattern from the lowest hop number to the maximum hop number. In the first reservation frame, the nodes which are one hop away from the sink allocate a certain set of slots. In the second reservation frame, the nodes which are two hops away from the sink allocate the slots and so on. In this case, the running time of ft_DTSM is fully dependent on the maximum hop number of the network.
Analytical models are developed to compare the run time performances of different time slot assignment algorithms.
Running time of FPRP which has five different signal phases is as follows: RFPRP = 5∗ time for one signal exchange slot ∗ total number of
reservation cycles in a reservation frame.
Running time of ft_DTSM is as follows: Rft_DTSM = 4∗ time for one signal exchange slot ∗ total
number of reservation cycles in a reservation frame ∗ maximum hop number + time for
advertisement slots∗maximum hop number.
In Figure 14, the average running time of ft_DTSM with different fault tolerance parameters and FPRP are compared, if it is assumed that every signal exchange slot has 5 bits and there are two guard bits between each signal exchange slots.
Running time of ft_DTSM and FPRP for different network size.
Running time performances are affected by the node density. A higher node density implies a longer run time, which stems from a higher contention rate. While ft_DTSM is a hop number based slot assignment algorithm, FPRP has a fully distributed slot assignment mechanism. In FPRP, all the nodes try to get a valid signal simultaneously. However, in ft_DTSM, higher hop numbered nodes wait for the lower hop numbered nodes to get a valid slot. In this case, FPRP always runs faster than ft_DTSM.
Run time differences between ft_DTSM with different fault tolerance parameters are more considerable in lower node densities. When the node density is lower, the number of neighbor nodes is also lower and finding an appropriate parent probability decreases. In this case, for a lower density network, the maximum hop number differences between different fault tolerance parameters are higher. On the other hand, in higher densities, the connectivity of the network is higher and the maximum hop numbers of ft_DTSM with different fault tolerance parameters are closer. In this case, the run times also become closer.
While FPRP and ft_DTSM can run in the order of seconds, simulation implemented in [20] has shown that DRAND takes approximately 25 seconds when node density is 1. DRAND run time fits a quadratic curve with varying node densities. When the node density is 5, DRAND takes approximately 240 s, which is much longer than the run time of FPRP and ft_DTSM. FLAMA also takes much longer than FPRP or ft_DTSM. It takes 55 s when the node density is 1 [34]. Its run time increases linearly with increasing node density. It shows that its run time for node density 5 is about 275 s.
In this article, a new delay sensitive, energy efficient, and fault tolerant distributed slot assignment algorithm for WSNs, referred to as ft_DTSM, is proposed. It assumes that the data traffic of a sensor network is convergecast and data always flow from higher hop numbered nodes to lower hop numbered nodes. Although any hidden node problem does not allow assigning the same node within two hop neighbors, ft_ DTSM can assign the same slot within two-hop neighbors relying on convergecast traffic assumption. ft_DTSM also has a special mechanism to tolerate failures of the sensor nodes. A discrete-event simulator is developed to compare ft_DTSM and common WSN distributed slot assignment algorithms. An extensive set of simulation results show that although energy consumption of ft_DTSM increases with a fault tolerance parameter, the energy consumption performance of ft_DTSM is superior to that of FPRP [13], DRAND [20], and FLAMA [34]. Moreover, ft_DTSM can also handle a delay problem successfully. Delay performance of ft_DTSM is also better than that of FPRP, DRAND, and FLAMA. Although the fault tolerance mechanism increases delay, ft_DTSM maintains its superiority with respect to the existing time slot assignment algorithms. With the help of a fault tolerance mechanism, ft_DTSM can distribute the time slots so that the sensor network can continue its operation even when many sensor nodes fail. Therefore, ft_DTSM supports more reliable network than FLAMA. Although ft_DTSM can realize low energy consumption, low delay, and high fault tolerance, its running time proportionally increases with the sensor network area and the fault tolerance parameter. Fortunately, due to its scalability, ft_DTSM can run with acceptable run times.