Adaptive duty-cycling to enhance topology control schemes in wireless sensor networks.
The wireless sensor networks are composed of a large number of low powered battery nodes needed to operate in an unattended status for a long duration. It is important to conserve the energy in activities of the nodes in order to keep the nodes alive and to make them run for a long period with limited energy capacity . Reducing the power consumption in communication is the most effective way to extend the lifetime of nodes, as wireless communication uses the majority of the energy among the operations of the nodes . Two strategies are generally used to reduce the energy consumption in wireless communication. One is to adjust the enough transmission power to reach the receiver node. The other one is to periodically schedule the nodes to switch from active mode to sleep mode to save energy during idle listening time.
Several approaches have been proposed to prolong the network lifetime by minimizing the transmission power of the nodes [3-5]. The major energy consumption of wireless sensor networks, however, is caused by the idle listening state but not by packet reception and transmission in a dense network or under light traffic  and reducing idle listening time is the most effective way to extend the lifetime. In sleep/wakeup protocols [7, 8], nodes follow a periodic cycle of sleep/active mode without considering the connectivity of the network. This approach can conserve energy by reducing the idle listening time. However, it can cause an additional data transmission delay in WSNs, as the intermediate nodes have to wait for the nodes at the next hop to wake up for receiving the data. In some WSNs applications requiring real-time communication, the transmission delay is one of the most important criteria to evaluate the success of the network. Several topology control approaches [9-12] have been proposed for the reduction of the energy consumption without incurring the critical data transmission delay in a dense sensor network.
The basic idea of topology control schemes is to divide the nodes into groups, and regardless of the selecting of a node from a group, all the active nodes can form a connected backbone network. Then, only the nodes that have the highest energy are selected in each group to take charge of an active radio mode. The other nodes can conserve their energy by putting their wireless devices into sleep status. These approaches can also reduce further transmission delay, as the network has been connected. However, they cannot guarantee well-balanced energy consumption among all the nodes because they cannot guarantee that each group consists of the same number of nodes. For example, there is a network as shown in Figure 1(a). The network consists of several groups created by topology control scheme. Nodes in the different groups use their energy unevenly at each other because each group consists of a different number of nodes. As a result, nodes in group 1 run out of energy faster compared to the nodes in the other groups. The region of group 1 will be a hole and then the network will be disconnected as shown in Figure 1(b). It must be ensured that all nodes have an equal lifetime, as they are equally vital to maintain the networks .
We propose an adaptive duty-cycling (ADC) scheme to enable well-balanced energy consumption among all the nodes, while minimizing any extra overhead in topology control schemes. The ADC scheme can be applied as a subprocess of the conventional topology control schemes. Regardless of the number of nodes present in a group, the traditional method of topological control scheme operates such that one node is in active radio mode from each group. That is, each group has a 100% duty-cycle in which one node is selected from each group to operate in an active radio mode at all times. But we will consider the number of nodes in each group. The group that has a large number of nodes will have a high duty-cycle, whereas the group that has a small number of nodes will have a low duty-cycle. In this paper, we also propose f-ADC scheme. The f-ADC scheme can be more effectively applied to various environments by adjusting the duty-cycle, which is determined by ADC scheme, based on the network traffic amount. This approach achieves that ADC scheme can balance the energy consumption between all nodes. To evaluate our scheme, we make in-depth simulations and show that ADC scheme extends the network lifetime by at least 25% compared to the conventional ones. Also, ADC scheme keeps the transmission delay as a constant during the network lifetime. It ensures reliable transmission delay. Moreover, ADC scheme uses distributed information and is executed only once at the earlier stage of the network. It has a low overhead and high scalability. At low traffic network, t-ADC scheme which is an extension scheme of ADC scheme extends the network lifetime by about 17% compared to ADC scheme.
The rest of the paper is organized as follows. We show the preliminary study about ADC scheme in Section 2. In Section 3, we describe our proposed ADC algorithm. We show the simulation results in Section 4. The last Section concludes the paper.
2.1. Assumptions and Definitions. This paper has the following assumptions. Each node consists of the communication module and sensing module. The energy consumption during sensing is negligible compared to wireless communication [14, 15]. In the wireless communication, the main energy consumption is used for idle listening, instead of packet transmission and reception. The duty cycling is an important mechanism for the reduction of energy consumption in sensor networks. The duty cycling technique saves energy by switching the wireless communication interface of each node between awake and sleeping, while the nodes always keep the sensing devices in an active status. If some data is sensed by the nodes whose wireless interface is in the sleep status, then these nodes can turn on their wireless components temporarily for the transmission of data and can return to sleep status after the completion of the data transmission .
We use the following terms. The size of the group is the number of nodes in a group. The maximum group size is the size of the group with the largest number of nodes in the network. In a network, every pair of adjacent groups is either a completely or arbitrarily adjacent group. As shown in Figure 2(a), two completely adjacent groups ensure the connection between these two groups whichever wireless interfaces of any one node from each group operate in active mode. As shown in Figure 2(b), two arbitrarily adjacent groups cannot guarantee the connection. It depends on the active nodes that are selected from each group.
2.2. Related Work. Without causing a serious data transmission delay in dense sensor networks, topology control schemes are to reduce the energy consumption. Topology control schemes use redundant nodes . Their purpose is to keep the connected backbone network by putting the minimum number of nodes in the active mode. In these schemes, the network lifetime can be prolonged because sleep nodes conserve their energy. Any extra communication data transmission delay can be reduced as these schemes guarantee the connectivity of the entire network. These topology control schemes are generally classified as location driven protocol and connection driven protocol . Typical examples of location driven and connection driven protocols are the geographical adaptive fidelity (GAF) [9,10] and connectivity-based partitioning approach (CPA) [11,12] schemes, respectively.
As shown in Figure 3, GAF [9, 10] divides the sensing area, where the nodes are distributed into multiple equal-size squared cells and each is with a side length of R/[square root of 5], where R is a radio transmission radius. A group is organized by the nodes in the same cell. After the grouping process, each group will select one node as the active status. This guarantees that any two nodes in the neighborhood cells are connected together, as their distance is within R. The entire network connectivity can be guaranteed by activating only one node from each group. GAF can ensure that all nodes in the same group have a similar lifetime by alternatively activating a node from the group. However, this scheme is not suitable for the real environment since it uses an ideal radio propagation model. Moreover, each group has four completely adjacent groups regardless of the traffic amount in the network, because the GAF divides the sensing area based on square grid structure.
CPA has overcome these limitations. CPA divides the nodes based on their connectivity, instead of their physical position. As shown in Figure 4(a), each node forms a group at the beginning of the grouping process. Then, the pairs of two completely adjacent groups merge into one group (Figure 4(b)). This process operates continually until the preset number of completely adjacent groups cannot be guaranteed [11,12]. Similarly in GAF, the connectivity of the entire network can be guaranteed by activating only one node from each group. By periodically changing the active nodes, CPA also guarantees that all the nodes in the same group have a similar lifetime. This implies that all nodes in the network are equally important. However, this scheme has a problem that nodes in groups with fewer nodes consume their energy relatively fast.
3. Proposed Scheme
We propose the ADC scheme (see Algorithm 1) which can be applied to the conventional topology control schemes in order to guarantee that all nodes in the network have a similar lifetime. Both GAF and CPA approaches only ensure that all nodes in same group have similar lifetime. However, no one can guarantee the same number of nodes in every group. This causes an unbalance in the energy consumption between different groups. Nodes in small size groups run out of energy faster compared to the nodes in large size groups. Although nodes in large size groups may have sufficient energy remaining, the network cannot guarantee seamless data transmission if the surrounding nodes run out of energy. Thus, the network lifetime in these conventional schemes reduces. Moreover, these schemes create completely adjacent groups to guarantee the connectivity of the entire network, whichever any one node operates in active mode from each group. In the process of creating these completely adjacent groups, a greater number of arbitrarily adjacent groups are formed rather than the completely adjacent groups, as shown in Figure 5. If only one node operates in the active mode from each group, then it is likely that the node will communicate with the nodes in arbitrarily adjacent groups and as well as in the completely adjacent groups. We need a way to enable all the nodes in the network to have a similar lifetime by using the communicable nodes.
We propose an adaptive duty-cycling (ADC) approach. ADC can be applied as a subprocess of the conventional topology control and ensure that all the nodes in the network have a similar lifetime. The basic idea of the proposed scheme is to group the nodes by using the topology control and then apply adaptive duty-cycle, depending on the group size. By this, the proposed scheme ensures that all the nodes in the network have a similar lifetime. For instance, GAF and CPA schemes always require any one node to operate in the active mode from each group. In ADC, if the maximum group size is 10, then the group formed by 10 nodes always operates any one node in an active mode during 10 unit times. Conversely, the group formed by 2 nodes operates any one node in the active mode for only 2 unit times out of 10 unit times. It means a 20% duty-cycle; all nodes in the group remain in sleep mode for the remaining 8 unit times. Our proposed scheme can guarantee balanced energy consumption among all nodes in the network using the adaptive duty-cycle based on group sizes. If ADC scheme is applied to the conventional schemes, such as GAF and CPA, then the connectivity of the network will decrease at the earlier stage of the network. However, the connectivity of the network deteriorates rapidly over time in the conventional schemes, because nodes in small size groups rapidly run out of energy. If ADC scheme is applied to the conventional schemes, then the initial connectivity of the network can be maintained during the lifetime. It can guarantee seamless communication.
3.1. ADC Approach. ADC scheme consists of two stages to guarantee that all the nodes in the network have a similar lifetime, as shown in Figure 6. One is to estimate the maximum group size based on the distributed information and the other one is designated to determine the duty-cycle for each group. Each group determines its own duty-cycle by comparing their group size with the maximum group size estimated in the first stage. With these two stages, ADC scheme assures balanced energy consumption among all nodes in the network.
At the first stage, the size of the group is broadcasted within two-hop distance by the head node of the group . After receiving the group size information of other groups, each head node estimates the average group size ([mu]) in the network in a dispersive manner. Then, the standard deviation ([sigma]) can be calculated by using
[sigma] = [square root of [n.summation over (k=1)] [([x.sub.k] - [mu]).sup.2]/(n - 1)] (1)
where [x.sub.k] is the size of the groups and n is the number of information for the group sizes received from the other groups within two-hop distance. If n is greater than 30, the group sizes known to the head node will follow the normal distribution, in accordance with the central limit theorem. According to the normal distribution, 99% of all the data are located within [mu] [+ or -] 2.58[sigma]. We can estimate the maximum group size ([M.sub.size]), after calculating the standard deviation on the group sizes as follows:
ALGORITHM 1: Adaptive duty-cycling algorithm. (1) for all hi [member of] H do /*hi: header nodes of each group, H: set of header nodes */ (2) broadcast own group size within 2 hop (3) end for (4) for all hi [member of] H do (5) calculate average group size ([mu]) using information received from the other headers (6) calculate standard deviation ([sigma]) using information received from the other headers (7) estimate maximum group size using [mu] and [sigma] (8) determine own duty cycle by comparing own group size with the maximum group size (9) end for
[M.sub.size] = [mu] + 2.58[sigma]. (2)
In the second stage, each group determines its duty-cycle based on the maximum group size estimated in the first stage. Here, the duty-cycle for each group is calculated based on the assumption that the largest group operates with 100% duty-cycle by using (3) to enable all the nodes to have similar activation times as follows:
[S.sub.Duty-Cycle] = 100 x [S.sub.size]/[M.sub.size] (3)
where [S.sub.Duty-Cycle] is the duty-cycle, [S.sub.size] is the group size, and [M.sub.size] is the maximum group size. By using (3), each group operates with a different duty-cycle based on the proportion of its group size to the maximum group size.
In some prior topology control approaches, such as GAF and CPA, each group has to turn on at least one node all the time. As no one can guarantee the same number of nodes in every group, the nodes in small size groups exhaust their energy faster compared to the nodes in larger groups. As a result, nodes in the network will have a different lifetime. By applying the adaptive duty-cycle depending on the group size, the proposed scheme ensures that all the nodes in the network have a similar lifetime. On the other hand, our proposed scheme maintains similar communication paths throughout the network lifetime. Our approach can be modularly applied to the conventional topology control schemes and is conducted only once. Therefore, it has the advantage of low overhead.
3.2. Application Method and Example. Our proposed scheme can be applied as an additional subprocess of the conventional topology control. In order to demonstrate how the approach is applied to conventional schemes, we group the nodes by using the conventional topology control approaches, GAF and CPA. 500 nodes, each with a transmission radius of [square root of 5], are deployed in the network with an area of 10 x 10. Table 1 shows the result of grouping the nodes based on GAF and CPA .
The mindeg value represents the number of completely adjacent groups in Table 1. As shown in Table 1, the number of groups, average group size, and the standard deviation on group sizes depend on the mindeg value. But neither GAF nor CPA can ensure that the groups have the same size. In order to demonstrate the differences between the group sizes in the conventional approaches, we can estimate the results shown in Table 2 by analyzing the GAF data from Table 1.
After grouping the nodes by using GAF or CPA, next step is to decide on the maximum group size in order to apply the proposed approach. In order to calculate the maximum group size, the head node of each group broadcasts its size within two-hop distance. Then, each head node dispersively calculates the average group size and the standard deviation on the group sizes based on the information received from other head nodes. After calculating the average group size and the standard deviation on the group sizes, each head node estimates the maximum group size by substituting these values in (2). If every head node is aware of the size information on at least 30 groups, the values estimated using the central limit theorem can be said to be reliable. In order to demonstrate this, this paper uses the data in Table 1 . According to Table 1, all the nodes are divided into 100 groups. In other words, 100 head nodes exist on a network with the size of 10 x 10, and if we use (4), then we can identify the number of other head nodes located within the transmission range of any one head node. Consider
The size of field : n = [pi] x [R.sup.2] : X, (4)
X = n x [pi] x [R.sup.2]/The size of field. (5)
The size of field
Here, the size of the field is 10 x 10. The number of head nodes, n, is 100. The radio transmission radius of each node, R, is [square root of 5], and X is the number of head nodes located within one-hop distance. If we substitute the above figures in (5), then, we will see that there are approximately 15 other head nodes within one-hop distance of each header node. Hence, if each head node broadcasts its size within two-hop distance, then each head node will obtain the information on at least 30 groups.
In real life, radio transmission radius of nodes is not in the form of unit disks but is rather distorted [17, 18]. Hence, the proposed approach should be applied to not only ideal but also real-life radio propagation models. As GAF is not valid in real-life radio propagation model, the proposed approach is applied to CPA to show that our scheme can be applied to real-life radio propagation model. In , the CPA creates more groups to work well in the real-life radio propagation model. Hence, as the radio propagation model in the real life tends to have small radio transmission radius compared to ideal ones, more groups will be created. As a result, even though the proposed approach is applied in real-life radio propagation model, the number of head nodes within one-hop distance is similar to ideal radio propagation model.
According to the maximum group size estimated by using the information received in a dispersive manner, the duty-cycle for each group is calculated by using (3). This is based on the assumption that the largest group operates with 100% duty-cycle. We use the values in Table 2 in order to demonstrate that each group has a different duty-cycle depending on its size: as maximum group size is 7, a group formed of 3 nodes will operate with a 43% duty-cycle. On the other hand, a group whose size is 7 will operate with a 100% duty-cycle as it has an equal size to the largest group. In other words, this group always has the active state node until all nodes in the group run out of energy. On the other hand, a group that contains 3 nodes will allow only one node in the active state for the 43% of the network lifetime, and all the other nodes will remain in the sleep mode for the rest of the lifetime, to reduce energy consumption. As a result, the proposed approach can ensure that all the nodes in the network have a similar lifetime.
Even though all the nodes are guaranteed an equal lifetime, the proposed approach will not be applicable if the data cannot be transmitted smoothly. The proposed approach must guarantee smooth data transmission. GAF provides 4 completely adjacent groups, and CPA ensures as many completely adjacent groups as the user needs. In order to guarantee the number of completely adjacent groups, more number of arbitrarily adjacent groups is created. If one node of each group operates in an active state, it is likely to communicate to the nodes that are in its arbitrarily adjacent groups as well as those in the completely adjacent groups. As shown in Figure 5, we can demonstrate this, by using Table 1 and (5). If one node of each group operates in an active state in GAF scheme, there will be about 15 other active nodes within one-hop distances. If we apply the ADC approach on Table 2, then the entire network has a duty-cycle of approximately 70%. If we apply this duty-cycle to Table 1 and (5), then it can be concluded that there are about 10 other active nodes within one-hop distances of each active node. Although routing paths reduce when the proposed scheme is applied to the conventional topology control approaches, the proposed approach ensures smooth and stable communication.
3.3. Analysis for Necessity of Proposed Scheme. All the nodes in the WSNs are equally important to minimize the coverage reduction. The proposed scheme which ensures a similar lifetime of all nodes is essential in terms of coverage. This section explains the validity and necessity of the proposed scheme in terms of data transmission by comparing the wireless sensor networks to real life.
In the sensor networks, the basic role of nodes is to sense the information and transmit it via either one hop or multihops towards the destination. These sensor networks can be compared to one of the large transport company. The information sensed by each node is a load that must be delivered to a destination by using a vehicle (wireless communication). The roads that are used to deliver the load by vehicles are the nodes and the lifetime of nodes can be compared to the lifetime of a road. Only if the state of roads (nodes) is in the active mode, then vehicles move. However, a major energy of nodes (roads) is usually used by listening among the communication processes, instead of packet reception and transmission . Reducing the time spent in listening to each road is the most effective way to extend the lifetime of the roads.
As shown Figure 7, the number of active roads in ADC is less than the number of active roads in GAF. It is the same reason stated for Sections 3.1 and 3.2. In order to deliver loads towards a destination, the vehicle on any road will move to other active roads that are located closer to the destination compared to its current location and are located within a distance R from its current location. Here, at the earlier stage of the network, GAF scheme delivers load to the destination faster than ADC scheme because GAF scheme compared to the ADC scheme has more active roads that can be used by a vehicle. However, the lifetime of roads in groups with fewer roads ends at relatively faster rates in GAF scheme. The number of available roads reduces fast over time compared to the earlier stage of the network. After a certain period, the topology of GAF and ADC schemes is changed as shown in Figure 8. Here, the proposed scheme delivers load to the destination faster than GAF scheme because the proposed scheme has more active roads than GAF scheme.
In other words, the number of available roads reduces fast over time in the GAF scheme, whereas ADC scheme always maintains similar number of available roads. It can be explained by using analogy as follows. In GAF scheme, if the transport company works for 15 days, it will use 10 roads from day 1 to day 5, 7~5 roads from day 6 to day 10, and 2~0 roads from day 11 to day 15 to deliver the load. As a result, although the transport company delivers the load rapidly at the earlier days, delivery speed of the load will decrease as days go by. On the other hand with GAF, in the proposed scheme, the transport company can guarantee a constant delivery speed on every day, as the company always uses 7 roads to deliver the load during the 15 days. Therefore, proposed scheme is more efficient compared to the previous scheme in terms of reliable data transmission. This explanation can be applied equally even if GAF scheme is changed by using the CPA scheme.
3.4. t-ADC Scheme. In the previous ADC scheme, we have only focused on guaranteeing whether all nodes have the same lifetime or not. As a result, it can achieve the similar lifetime for all nodes in the network and reliable data transmission. However, ADC scheme does not consider the various network environments (e.g., traffic amount) where the nodes are deployed. In other words, in ADC scheme, each group decides its duty-cycle depending on just the group size without the consideration of the network environments. Although, by using this way we can guarantee similar lifetime for all nodes in the network; it lacks adaptability in accordance with the various network environments. If ADC scheme can be changed depending on network environment, where nodes are deployed, it will be a more efficient scheme. For example, ifeach group reduces its duty-cycle in low-traffic network, network lifetime will be significantly extended, whereas additional end-to-end communication delay is not big.
In this subsection, we propose the f-ADC scheme which is based on ADC scheme and it can adjust flexibly the duty-cycle of each group based on network environment factor (i.e., traffic amount) where a wireless sensor network is applied. In f-ADC scheme, each group decides its duty-cycle by using
[S.sub.Duty-Cycle] = t 100 x [S.sub.size]/[M.sub.size], (6)
where [S.sub.Duty-cycle] is the duty-cycle, [S.sub.size] is the group size, and [M.sub.size] is the maximum group size. It is similar to ADC scheme. The traffic constant (f) is determined by the administrator and it is based on the traffic conditions of the application when a sensor network is deployed. Here, by multiplying the traffic constant (f), f-ADC schemes can be more flexibly applied to various environments. The maximum value of the traffic constant is 1 and the lower the traffic amount of the network is, the lower the value of traffic constant is. In order to show the effectiveness of f-ADC scheme, this paper simulates the ADC and f-ADC schemes while changing the range of the traffic constant value from 0.8 to 1 at environment of . The result of simulation shows that f-ADC scheme extends the network lifetime by about 17% compared to ADC scheme without the incurring critical data transmission delay regardless of network environments.
4. Performance Evaluation
4.1. Simulation Environment. We implement the simulation by using Java to analyze the performance of the proposed scheme. We use two ways to assure the reliability of the simulation. First, we conduct the simulation in accordance with the same environment in , and we obtain the same trends from the graphs that represent the network lifetime. Second, all the experiments are repeated 1,000 times. As shown in Table 3, default simulation environments are as follows. We uniformly deploy 500 nodes, each with a transmission radius of a/5, in the network with an area of 10 x 10. The ratios of the amount of energy used in the transmitting, receiving, and listening status are 1.7: 1.2: 1, respectively . The initial energy of each node is set to 500. So, each node will remain alive during 500 unit times in the listening mode. The simulations are conducted based on the assumption that the energy consumption is uniform over all the nodes, regardless of the location of the sink node by using the mobility-assisted approaches in order to evaluate the algorithm more accurately [19,20]. Twenty pairs of source and sink nodes are randomly selected in each time slice . Load balanced short path routing  is used as the routing protocol, and the network lifetime is defined as the time a certain ratio of the nodes runs out of energy [22, 23]. As shown in Table 3, some simulation environments are changed in each subsection. In this case, we state the new simulation parameters at the beginning of each subsection.
4.2. Network Lifetime. The number of dead nodes that run out of energy over time, when 200 and 400 nodes are deployed in the network, is illustrated by using Figures 9(a) and 9(b), respectively. The horizontal axis represents the unit time (i.e., the time elapsed from the beginning of the simulation) and the vertical axis shows the number of living nodes. As shown in Figure 9(a), the first dead node appears around 500 unit times in the GAF and CPA schemes, and the number of living nodes decreases in the pattern of steps over the next 700 unit times. On the other hand, when the proposed scheme is applied to GAF and CPA, the first dead node appears at about 1,500 unit times, and the number of the living nodes decreases in a steep curved pattern. Due to the different size of a group in the network, nodes consume very different amounts of energy in conventional approaches; some nodes run out of energy very quickly. Thus, the number of living nodes decreases in a pattern of steps over a long time. In contrast, the proposed scheme applies the adaptive duty-cycle depending on the group sizes and this enables all the nodes to have a similar lifetime. Therefore, the number of living nodes sharply decreases over a short time. Moreover, when the proposed approach is adapted, some groups convert all their nodes to sleep mode. Thus they can conserve the energy and can cause an extension of the overall network lifetime for conventional approaches.
Figure 10 shows the number of dead nodes over time, after 500 nodes are deployed in the network. The experiments are implemented under different number of completely adjacent groups (=mindeg). In GAF and CPA, the first dead node occurs around 1,000 unit times, and the number of living nodes decreases following a step pattern over the next 1,500 unit times. Moreover, by applying the proposed scheme to the GAF and CPA, the first time when a dead node appears is about 3,000 unit times. During the next 200 unit times, the number of living nodes decreases quickly which is similar to a steep curved pattern. By applying the proposed approach we can balance the lifetime of nodes and increase the network lifetime. Besides, regardless of the node density, we can ensure an even lifetime for nodes in the network by applying the proposed approach to GAF and CPA. We can also minimize the coverage reduction of the network that results due to the energy depletion of nodes. The experiment results show that the network lifetime is improved by up to 25% compared to the conventional approach.
Figure 11 shows the times when certain ratios of the nodes in a network have consumed all their energy in the conventional approaches and applying the proposed scheme to these. The horizontal axis represents the percentage of the dead nodes in the network. The vertical axis represents the unit time, which is the time elapsed from the beginning of the simulation. When GAF and CPA are applied, 25 nodes (5%) consume all their energy at 1,600 and 1,500 unit times, respectively, after the simulation has begun. 450 nodes (90%) run out of their energy at 2,300 and 2,700 unit times, respectively. It can be deduced that it takes about 1,000 unit times until the next 85% of the entire nodes consume all their energy after the first 5% do. On the contrary, if the proposed approach is applied in addition to GAF and CPA, 25 nodes (5%) of the entire nodes consume all their energy at 3,000 and 3,250 unit times, respectively, after the start of the simulation. 450 nodes (90%) consume all their energy at 3,150 and 3,400 unit times. In other words, the differences in the lifetime of nodes in a network are as much as 1,000 unit times when the conventional approaches are used, whereas the difference in the lifetime between the nodes is significantly reduced to only 150 unit times when the proposed approach is applied. This is due to the proposed approach which uses adaptive duty-cycle. By using such an approach, the ADC ensures even lifetime for all the nodes and it can reduce the coverage reduction of a network that results from the dead nodes.
4.3. Transmission Delay. The transmission delay ratios for successful data of CPA and CPA with ADC are shown in Figure 12. The transmission delay for successful data is the time taken for successfully transmitting the data from the source node to the sink node. This delay ratio (vertical axis of Figure 12) can be calculated by using
Ratio of delay
= Delay for successful [transmissions.sub.CPA with ADC] / Delay for successful [transmissions.sub.CPA]. (7)
If ADC is applied to CPA, the value of the delay ratio is greater than 1 at the earlier stage of the network (500 unit times). This result implies that ADC yields longer data transmission delay. It is because some groups in the network may convert all their nodes to sleep mode and the corresponding communication paths for those groups cannot be used. On the other hand, conventional approaches can use all the communication paths by sequentially activating a node for each group. However, the value of the delay ratio gets smaller over time and it becomes less than 1 after 1,000 unit times, and the value of the delay ratio decreases over time. This result implies that the ADC has shorter data transmission delay compared to CPA, and the difference in their data transmission delay time increases over time. These results can be explained as follows. In the conventional schemes, the energy consumption of the nodes is uneven. Due to the uneven energy consumption of nodes, some nodes may deplete its energy much more quickly compared to others. In contrast, by applying the proposed scheme to conventional schemes, similar communication paths can be maintained throughout the network lifetime as the proposed scheme guarantees a similar lifetime of nodes. As a result, our scheme can guarantee consistent and reliable data transmission.
Figure 13 shows the relationship between the ratio of the cumulative data transmission delay for successful data and the number of dead nodes, under CPA and CPA with ADC. The left vertical axis is the ratio between CPA and CPA with ADC for the cumulative time taken for the successful transmissions to the sink node. The right vertical axis represents the number of dead nodes. The number of dead nodes increases over time in CPA, while dead nodes do not appear until 2,500 unit times when the proposed scheme is applied. The data transmission delay of CPA with ADC is larger compared to that of CPA at the earlier stage of the network. The reason is similar to that mentioned for Figure 12. The ratio of the cumulative data transmission delay for CPA and CPA with ADC is less than 1 at a later stage than that of the noncumulative delay illustrated in Figure 12. This is due to the cumulative data transmission that accrues time for the data transmission delay of the previous successful dates. However, there is virtually no difference between the data transmission delays for the two approaches when the standard deviation for them is taken into account. Moreover, we can observe that after a certain period of time, the transmission delay is shorter under CPA with ADC. As shown in Figure 13, it can be explained as follows. In CPA, the energy consumption of the nodes in the network is uneven and this causes some nodes to exhaust much more quickly compared to others. On the other hand, all the nodes in the network remain alive in CPA with ADC.
Figure 14 shows the relationship between the ratio of cumulative communication delay and the number of failed transmissions, under CPA and CPA with ADC, respectively. The left vertical axis represents the ratio between CPA and CPA with ADC for the cumulative time taken of successful communications to the sink nodes. The right vertical axis shows the number of failed transmissions. In order to compare the network connectivity of CPA and CPA with ADC, we assume that there is no collision occurring in the MAC (Media Access Control) layer such as . At the earlier stage of the network, no failure appears in CPA and in CPA with ADC. However, after 2,300 unit times, the number of failed transmissions increases rapidly under the CPA approach. This can be explained from the following. If a conventional approach is applied, the energy consumption of the nodes is uneven and it causes some nodes to exhaust much more quickly compared to others. On the other hand, our proposed scheme ensures that all the nodes have similar lifetime. Our scheme maintains good network coverage and it also guarantees reliable communication by maintaining an even level of data transmission delay.
4.4. Balanced Energy Consumption of Nodes. Through the entropy method, Section 4.4 shows that the proposed approach enables nodes in a network to have similar lifetime and to consume energy at even rates. "Entropy" is a criterion of randomness, and it is known that all substances on earth follow entropy. In other words, they tend to disperse evenly rather than gathering in one space. The entropy value for the given data set S is calculated by using (8)  as follows:
Entropy (S) = -[k.summation over (i=1)] [p.sub.i] x ln ([p.sub.i]), (8)
[p.sub.i] = freq ([C.sub.i], S)/[absolute value of S]. (9)
In (8) and (9), S is the set of given data and C is the set of classes from [C.sub.i] to [C.sub.k]. The class implies a set of data that meets a specific character. freq ([C.sub.i], S) is the number of data that belong to [C.sub.i] in the data set S, and [absolute value of S] is the number of data in S. As the data given in (8) evenly disperses to many classes, the entropy values will also increase.
Figure 15 shows the entropy under CPA and CPA with ADC, respectively, when 500 nodes are deployed in a network. The initial energy of each node is set to 500 and this implies that the node will remain alive for 500 unit times in the listening state. The vertical axis represents the entropy, which is the energy distribution of the nodes and it can be calculated by using (8) and (9). In these equations, class [C.sub.i] is divided into different energy levels, each with a range of 50 (i.e., 0~49, 50~99, etc.). Therefore, a total of 10 classes are formed, from [C.sub.1] to [C.sub.10]. S represents the energy of each node, and [absolute value of S] is the total number of nodes in the network which is 500. Figure 15 shows that the entropy value can be as high as 2.2 when CPA is applied. Meanwhile the value of entropy is lower than 1.3 when CPA with ADC is applied. As higher entropy values imply uneven energy distribution among entire nodes in a network, our proposed scheme is more effective in ensuring that all nodes use a similar amount of energy during their lifetime.
4.5. Network Lifetime and Transmission Delay under Different Network Scales. Figure 16 shows the network lifetime when we fix the node density to five nodes per square unit and run CPA and CPA with ADC on networks of different scales. The horizontal axis represents the network scale and the vertical axis represents the network lifetime. Here, network time is defined as the time when the first transmission fail occurs. As shown in Figure 16, when the network scale is 5 x 5, the lifetime of CPA and CPA with ADC is about 1,900 and 2,600 unit times, respectively. The proposed scheme prolongs the network lifetime by about 37% compared to the conventional one in 5 x 5 network size. Figure 16 also shows that, when the network size is large, the network lifetime of both CPA and CPA with ADC is longer because if the network size increases in same traffic amount condition, ratio of nodes, which are directly concerned with traffic, reduces. Here, an important aspect to be noted is that the proposed scheme always extends the network lifetime by about 38% compared to the conventional one regardless of the network size.
Figure 17 shows the ratio of the cumulative data transmission delay for successful data of CPA and CPA with ADC. Simulation parameters of Figure 17 are equal to Figure 16. The vertical axis represents the ratio between CPA and CPA with ADC for the cumulative time taken for successful transmissions to the sink node. This ratio value is greater than 1 at 500 unit times, the earlier stage of the network regardless of the network size. It implies that the data transmission delay is longer when the ADC is applied to CPA, and the reason is similar to that described in Section 4.3. The ratio value of a network with 25 x 25 scale is the lowest at 500 unit times. The reason is that when the network size increases in the same traffic amount the effect of the traffic amount will decrease. Here, an important aspect to be noted is that the ratio value decreases over time regardless of the network scale. It implies that ADC causes shorter data transmission delay compared to CPA. We have already explained the reason for this in Section 4.3. Here, the data transmission delay of CPA and CPA with ADC cannot be compared in a network with a network scale 5 x 5, after 2,000 unit times, because network lifetime is over before 2,000 unit times. For a similar reason, we cannot compare the data transmission delay of CPA and CPA with ADC in a network with a network scale from 5 x 5 to 20 x 20, after 3,000 unit times.
4.6. t-ADC Scheme. This subsection evaluates the i-ADC scheme which we discuss in Section 3.4. Here, to assume low traffic network, five pairs of source and sink nodes are randomly selected in each time slice. In Figure 18, when the traffic constant is 1, ADC scheme is the same as i-ADC scheme. When the traffic constant is 0.9, duty-cycle of each group in t-ADC scheme is 90% of that of ADC scheme.
Figure 18 shows the network lifetime of ADC and t-ADC scheme when the traffic constant is changed from 0.8 to 1. The horizontal axis represents the unit time (i.e., the time elapsed from the beginning of simulation) and the vertical axis shows the number of living nodes. Similarly in Section 4.2, first dead node occurs at around 1,000 unit times in CPA scheme, and the number of living nodes decreases in the pattern of steps over time. On the other hand, when t-ADC scheme is applied to CPA, similar lifetime is guaranteed for all the nodes. Figure 18 also shows that, as the traffic constant is low, network lifetime is extended and this is because the smaller the traffic constant is, the bigger the sleeping ratio will be. When the traffic constant is 0.8, the network lifetime is extended by about 17% compared to the traffic constant which is 1.
Figure 19 shows the ratio of the cumulative delay for successful transmissions of CPA and CPA with t-ADC. Simulation parameters of Figure 19 are equal to Figure 18. The vertical axis represents the ratio between CPA and CPA with t-ADC for the cumulative time that is taken for the successful transmissions to the sink node. Similarly, in Section 4.3, the ratio value is greater than 1 at 500 unit times, the earlier stage of the network regardless of traffic constant. It implies that the data transmission delay is longer when proposed scheme is applied to CPA. Moreover, the smaller the traffic constant is, the larger the ratio value is because, as traffic constant is small, the number of active nodes decreases. However, an important aspect to be noted is that the ratio value decreases over time regardless of the traffic constant, and the proposed scheme eventually guarantees faster data transmission delay compared to CPA.
In this subsection, we compare the lifetime and data transmission delay of CPA and CPA with i-ADC while the traffic constant is varied. Here, we show that, when the traffic constant is 0.8, ratio of data transmission delay is increased by about 7% compared to traffic constant which is 1, whereas network lifetime is extended by about 17%. It is because network is a low traffic environment (i.e., in low traffic network, even if sleeping ratio of each group is enlarged, the additional data transmission delay is not longer, whereas network lifetime is considerably extended). If we adjust duty-cycle of each group based on the network traffic environment, network lifetime is efficiently extended.
In this paper, the ADC approach is proposed in order to balance the energy consumption of the nodes. ADC approach can be used as a supplement scheme for other conventional protocols such as GAF and CPA. Simulation results show that, by applying the proposed scheme to these protocols, the network lifetime is improved by at least 25% and the energy consumption is guaranteed equally among the nodes. And the proposed scheme guarantees more reliable communication compared to other protocols and it has a low overhead because it is executed only once at the earlier stage of the network. Moreover, it uses distributed information so that it enhances the scalability of proposed scheme. We also propose i-ADC scheme which makes ADC scheme more flexible to adapt to various environments. Simulation results show that i-ADC scheme efficiently extends the network lifetime by adjusting the duty-cycle of each group based on the traffic environments of network where nodes are deployed.
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
This research was supported in part by MSIP (KEIT) and MOE (NRF), the Korean government, the IT R&D Program (10041244, SmartTV 2.0 Software Platform), and BSRP(NRF-2011-0014020)/PRCP(NRF-2010-0020210), respectively.
 D. Ganesan, A. Cerpa, W. Ye, Y. Yu, J. Zhao, and D. Estrin, "Networking issues in wireless sensor networks," Journal of Parallel and Distributed Computing, vol. 64, no. 7, pp. 799-814, 2004.
 B. S. Krishnan, M. Ramaswamy, and N. Alamelu, "Optimising energy* delay metric for performance enhancement of wireless sensor networks," International Journal of Engineering Science and Technology, vol. 2, no. 5, pp. 1289-1297, 2010.
 R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," in Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '00), vol. 2, pp. 404-413, Tel Aviv, Israel, March 2000.
 R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc networks," in Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '01), vol. 3, pp. 1388-1397, Anchorage, Alaska, USA, April 2001.
 N. Li and J. C. Hou, "FLSS: a fault-tolerant topology control algorithm for wireless networks," in Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom '04), pp. 275-286, Philadelphia, Pa, USA, October 2004.
 M. Medidi and Y. Zhou, "Extending lifetime with differential duty cycles in wireless sensor networks," in Proceedings of the 50th Annual IEEE Global Telecommunications Conference (GLOBECOM '07), pp. 1033-1037, Washington, DC, USA, November 2007.
 W. Ye, J. Heidemann, and D. Estrin, "An energy-efficient MAC protocol for wireless sensor networks," in Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '02), vol. 3, pp. 1567-1576, New York, NY, USA, June 2002.
 T. van Dam and K. Langendoen, "An adaptive energy-efficient MAC protocol for wireless sensor networks," in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), pp. 171-180, Los Angeles, Calif, USA, November 2003.
 Y. Xu, J. Heidemann, and D. Estrin, "Geography-informed energy conservation for ad hoc routing," in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom '01), pp. 70-84, Rome, Italy, July 2001.
 Y. Xu, S. Bian, Y. Mori, J. Heidemann, and D. Estrin, "Topology control protocols to conserve energy in wireless ad hoc networks," Tech. Rep., 2003.
 Y. Ding, C. Wang, and L. A. Xiao, "Connectivity based partition approach for node scheduling in sensor networks," in Proceedings of the 3rd IEEE International Conference on Distributed Computing in Sensor Systems, Santa Fe, NM, USA, June 2007
 Y. Ding, C. Wang, and L. Xiao, "An adaptive partitioning scheme for sleep scheduling and topology control in wireless sensor networks," IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 9, pp. 1352-1365, 2009.
 Y. Obashi, H. Chen, H. Mineno, and T Mizuno, "An energy-aware routing scheme with node relay willingness in wireless sensor networks," International Journal of Innovative Computing, Information and Control, vol. 3, no. 3, pp. 565-574, 2007
 G. Anastasi, M. Conti, M. Di Francesco, and A. Passarella, "Energy conservation in wireless sensor networks: a survey," Ad Hoc Networks, vol. 7, no. 3, pp. 537-568, 2009.
 B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, "Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks," in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom '01), pp. 85-96, Rome, Italy, July 2001.
 D. L. Trong and H. Choo, "Efficient flooding scheme based on 2hop backward information in ad hoc networks," in Proceedings of the IEEE International Conference on Communications (ICC '08), pp. 2443-2447, Beijing, China, May 2008.
 G. Zhou, T. He, S. Krishnamurthy, and J. A. Stankovic, "Models and solutions for radio irregularity in wireless sensor networks," ACM Transactions on Sensor Networks, vol. 2, no. 2, pp. 221-262, 2006.
 G. Zhou, T He, S. Krishnamurthy, and J. A. Stankovic, "Impact of radio irregularity on wireless sensor networks," in Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services (MobiSys '04), pp. 125-138, Boston, Mass, USA, June 2004.
 J. Luo and J.-P. Hubaux, "Joint mobility and routing for lifetime elongation in wireless sensor networks," in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM '05), vol. 3, pp. 1735-1746, Miami, Fla, USA, March 2005.
 W. Wang, V. Srinivasan, and K.-C. Chua, "Using mobile relays to prolong the lifetime of wireless sensor networks," in Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom '05), pp. 270-283, Cologne, Germany, September 2005.
 Z. Fan, "Prolonging lifetime via mobility and load-balanced routing inwireless sensor networks," in Proceedings of the 23rd IEEE International Symposium on Parallel & Distributed Processing (IPDPS '09), pp. 1-6, Rome, Italy, May 2009.
 F. Shen, M.-T. Sun, C. Liu, and A. Salazar, "Coverage-aware sleep scheduling for cluster-based sensor networks," in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '09), pp. 1-6, Budapest, Hungary, April 2009.
 Y. Chen and Q. Zhao, "On the lifetime of wireless sensor networks," IEEE Communications Letters, vol. 9, no. 11, pp. 976-978, 2005.
 Y.-J. Han, M.-W. Park, and T.-M. Chung, "SecDEACH: secure and resilient dynamic clustering protocol preserving data privacy in WSNs," in Computational Science and Its Applications--ICCSA 2010, vol. 6018 of Lecture Notes in Computer Science, pp. 142-157, Springer, Berlin, Germany, 2010.
 L. Feinstein, D. Schnackenberg, and D. Kindred, "Statistical approaches to DDoS attack detection and response," in Proceedings of the DARPA Information Survivability Conference and Exposition (DISCEX '00), vol. 1, pp. 303-314, Washington, DC, USA, April 2003.
Myungsu Cha, (1) Mihui Kim, (2) Dongsoo S. Kim, (3) and Hyunseung Choo (4)
(1) Mobile Communications Business of Samsung Electronics, 416 Maetan-dong, Yeongtong-gu, Suwon-si, Gyeonggi-do 442-742, Republic of Korea
(2) Department of Computer & Web Information Engineering, Computer System Institute, Hankyong National University, 327 Jungangro, Anseong-si, Gyeonggi-do 456-749, Republic of Korea
(3) Department of Electrical and Computer Engineering, Indiana University-Purdue University Indianapolis, 723 West Michigan Street, SL160, Indianapolis, IN 46202, USA
(4) College of Information and Communication Engineering, Sungkyunkwan University, 2066 Seobu-ro, Jangan-gu, Suwon-si, Gyeonggi-do 440-746, Republic of Korea
Correspondence should be addressed to Hyunseung Choo; firstname.lastname@example.org
Received 5 July 2013; Accepted 9 December 2013; Published 12 February 2014
Academic Editor: Chang Wu Yu
TABLE 1: Partitions of GAF and CPA. Number Average Standard deviation Partition approach of groups group size on group size CPA (mindeg = 2) 71 7 0.92 CPA (mindeg = 3) 84 6 0.77 CPA (mindeg = 4) 91 5.5 0.79 GAF 100 5 0.73 CPA (mindeg = 5) 106 4.7 0.67 CPA (mindeg = 6) 116 4.3 0.63 TABLE 2: Analysis on distribution of group size. Group size Distribution of group size 3 4 5 6 7 Number of groups 3 14 66 14 3 TABLE 3: Summary about simulation method. Compared schemes GAF, CPA, GAF with ADC, and CPA with ADC Lifetime Performance metrics Transmission delay Balanced energy consumption Parameters Number of nodes: 500 Network size: 10 x 10 Default Mindeg in case of CPA: 4 Traffic: 20 pairs of sink and source nodes (each time slice) Section 4.2 Number of nodes: 200, 400, and 500 Mindeg in case of CPA: 3, 4, and 5 Number of nodes: 125, 500, 1125, 2000, Section 4.5 and 3125 Network size: 5 x 5, 10 x 10, 15 x 15, 20 x 20, and 25 x 25 Section 4.6 Traffic: 5 pairs of sink and source nodes (each time slice) Routing Load balanced short path routing Other environments Same as environment in CPA
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||Research Article|
|Author:||Cha, Myungsu; Kim, Mihui; Kim, Dongsoo S.; Choo, Hyunseung|
|Publication:||International Journal of Distributed Sensor Networks|
|Date:||Jan 1, 2014|
|Previous Article:||ECN-based congestion probability prediction over hybrid wired-wireless networks.|
|Next Article:||Framework for a cloud-based multimedia surveillance system.|