Abstract: Sensing coverage and network connectivity are two main requirements which maintain perfect operation of wireless sensor network. Joint scheduling method has considered both requirements by using random scheduling for sensing coverage, which divides sensor nodes to k subsets. Each sensor nodes randomly selects one defined subset. Then, the algorithm turns on extra sensor nodes, if necessary for network connectivity. As Extra-on sensor nodes participate in other nodes routing, some of them may be subject of many times transmission and reception. Furthermore, some of Extra-on nodes should be active the whole time to create network connectivity. Both mentioned reasons can drain out energy of those extra active nodes and may lead to network partitioning. Hence, reducing number of Extra-on nodes is important. In this study, we utilize probing mechanism scheduling in joint scheduling method to reduce the number of extra on sensor nodes. By using probing mechanism that some nodes change their working schedule, number of extra on nodes reduces by 20%.
INTRODUCTION
Wireless Sensor Networks (WSNs) consist of large number of tiny sensor nodes. Each sensor consists of sensing, data processing and communicating components. The sensor nodes will perform significant signal processing, computation and network self-configuration to achieve scalable, robust and long-lived networks (Cerpa and Estrin, 2004). More specifically, sensor nodes perform local processing to reduce communications and consequently, energy costs. Due to small dimension of sensor nodes within several cube millimeters (Warneke et al., 2001), they have very limited power supply. Moreover, because of large number of sensors or hostile environment, charging or changing the battery is impossible. Hence, energy efficiency is an important concern for WSNs to operate for the long time using limited battery power.
Most of wireless sensor network applications use random deployment method by reason of hostile environment or large number of sensor nodes. In random deployment method, number of deployed sensor nodes is more than optimal deployment. If all the deployed sensor nodes simultaneously operate in the active mode, an excessive amount of energy would be wasted. In this case excessive packet collision will occur if many sensors intend to send packets. A fundamental issue is to minimize the number of nodes that remain active, while still achieving acceptable quality of service or sensing coverage and network connectivity for applications. Sensing coverage for sensing the area and detection of the events can be considered as the measure of quality of service of sensor network (Yan et al., 2003). The unit area is covered if any point in that area is within sensing range of an active node. The network is connected if any active node can communicate with any other active node. With connectivity information collected by sensing coverage can be sent to sink or base station. Some researches are only concentrated on coverage problem (Yan et al., 2003; Abrams et al., 2004; Hsin and Liu, 2004; Tian and Georganas, 2002; Wu et al., 2005; Ye et al., 2003;Wang et al., 2008), while some of them are topology management protocols that maintain the network connectivity (Cerpa and Estrin, 2004; Chen et al., 2002; Schurgers et al., 2002; Xu et al., 2003). Shakkottai et al. (2003), Liu et al. (2006), Tian and Georganas (2005), Wang et al. (2003), Zhang and Hou (2005) and Zhao and Gurusamy (2008) have considered both problem of coverage and connectivity.
In this research that deals with both problem of sensing coverage and network connectivity, some of Extra-on nodes should participate in many nodes routing. So, they are subject of many times transmission and reception. For this reason, their energy will be reduced rapidly in addition to energy consumption for being active in extra subset. Our probing mechanism that reschedules some of sensor nodes is capable of reducing the number of extra-on sensor nodes. In this research, each active sensor node knows at least one shortest path to the sink node. So, no additional routing protocols are needed.
Selecting a minimal set of active nodes in energy efficient connected coverage protocols reduces power consumption and prolongs network life time. These protocols consider sensing coverage and network connectivity requirements at the same time. In continue several connected coverage algorithm will be presented.
Zhang and Hou (2005) have proved that if the radio range is at least twice the sensing range, a complete coverage of a convex area implies connectivity among the active sensor nodes. Tian and Georganas (2005) enhanced the work Zhang and Hou (2005) by proving that: if the original network is connected the communication range of twice the sensing range is sufficient condition and the tight lower bound to ensure the complete coverage implies connectivity among active nodes. They also extend their result to k-degree connectivity and k-degree coverage.
In Wang et al. (2003), the authors proposed Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. They have proved that with CCP sensing coverage implies network connectivity when the sensing range is no more than half of the communication range. For the case when the communication range is less than twice of the sensing range, the authors have integrated CCP with Chen et al. (2002) to provide both coverage and connectivity.
Liu et al. (2006) have proposed joint scheduling method. This method uses random scheduling for sensing coverage. For ensuring connectivity extra sensor nodes are turned on. In Lin and Chen (2008), the authors have presented a distributed approach for assisting the work Liu et al. (2006) to provide the full coverage.
ALGORITHM DEVELOPMENT
Sensing coverage and network connectivity explained in the following are two main parts of the algorithm. This research work is differentiated from Liu et al. (2006) work with the probing mechanism step in connectivity part.
Sensing coverage: For sensing coverage randomize scheduling algorithm will be performed that does not assume the availability of any location or directional information. It is a purely distributed algorithm thus scalable for large networks.
| Fig. 1: | Typical randomized coverage-based algorithm |
| Fig. 2: | Example of upstream and downstream nodes |
If sensor nodes constitute a set S and k is given as number of subsets, k working subsets will be defined. At the time when sensor nodes are scattered in the area, each of them randomly joins one of the k disjoint subsets. When the network is dense enough, each subset will cover almost the whole area. The k disjoint subsets will work alternatively. Figure 1 shows an example. Sensor nodes with IDs 0, 1..., 7 randomly deployed in the field. Given number 2 as k, any sensor randomly selects 0 or 1 and joins one of the corresponding subsets S0 or S1. If sensor nodes 0, 3, 4, 6 select number 0 and thus join subset S0 and sensor nodes 1, 2, 5, 7 select number 1 and join subset S1. When sensor nodes with IDs 0, 3, 4, 6 shown by solid circles are active, sensor nodes with IDs 1, 2, 5, 7 shown by dashed circles, fall asleep and vise versa.
Assume all sensor nodes know their minimum hop count to the sink node S. Between two neighbors, node with less number of minimum hop count is called upstream node that is closer to the sink node. Node with more number of minimum hop count is called downstream node. In Fig. 2, node A is within communication range of sink, so A is sink’s neighbor with communication range of 1. B and C are within communication range of A, they get minimum hop count of 2. Node A is upstream of B and C and nodes B and C are downstream nodes of A.
Network connectivity: After performing randomize scheduling algorithm, k subnetworks will be formed in the network, each of them corresponds to a specific subset and consists of all the nodes assigned to that subset. Using the following steps ensures that each subnetwork is connected, given that the original network before scheduling is connected. Besides, it also guarantees that any sensor node to the sink node has at least one shortest path.
Extra-on rule: If a sensor node A has a downstream node B, which is active in time slot i and if none of node B’s upstream node is active in that time slot, then node A should also work in time slot i. In other words, besides working in duty cycles assigned by the randomized coverage-based scheduling, node A is required to work in extra time slots, e.g., time slot i in this case. To enforce the extra-on rule the following steps should be performed:
| • | Step 1: Propagate the minimum hop count: In this step propagation of Hop advertisement message will be started from sink node. The hop advertisement message contains the minimum hop count to the sink, the nodeID and its subset decision. Initially, the minimum hop count is set to 0, in the broadcasting packet from the sink and sensor nodes minimum hop count is set to infinity. When a node receives a hop advertisement message, will put the message in its buffer and before the rebroadcast of hop message the hop count value in the hop message will increase by 1. Each node may receive different hop count value from neighboring nodes. But it suppresses nonminimal hop count value and only rebroadcasts the minimum hop count value after a backoff time. If no packets are lost, at the end of this step, each sensor node will obtain the minimum hop count to the sink node. Although, collisions or poor channel quality may cause packet lost. However, packet losses will not impact the successful operation of algorithm, i.e., the network will still be connected even if some nodes may have only a nearly shortest path to the sink node |
| • | Step 2: Exchange information with local neighbors: Each sensor node locally broadcasts its minimum hop count, its nodeID, its subset decision, the nodeIDs of its upstream nodes and their subset decisions. The upstream nodes are the nodes from which the current node receives its minimum Hop count. Each sensor node records and maintains all the information it receives from its immediate neighbors |
| • | Step 3: Probing Mechanism to change nodes working schedule: After random deployment in the step 1 each node has randomly joined to one subset. To ensure network connectivity each node needed to find route to the sink through its upstream nodes. If node could not find an upstream node working in node’s subset, it conduced to create one extra-on node i.e., one of the upstream nodes should work in extra subset. This denotes that to reduce the number of extra-on nodes, upstream nodes of each node should work in node subsets. But in the case of nodes randomly joining to subsets, it may impossible for some upstream node to contain downstream nodes subsets. In the probing mechanism step each node probes its upstream nodes subsets and change one of the more repeated subsets to its subset. Nodes subsets can only change once in this step. This step starts from nodes with maximum hop count towards sink node. This step is actually the reverse process of step 1 |
Figure 3a and b show an example. Given k equal 3, there are three subsets k0, k1 and k2. Node A works in subset k0 and is searching routes toward sink node. To avoid creating extra-on nodes, one of the upstream nodes of A should work in subset k0. In Fig. 3, nodes B, C, D, E and F are A’s upstream nodes. Initially these nodes subsets are k1, k1, k2, k2, k2 respectively. Maximum repeated subset is k2, while any node doesn’t work in subset k0. Node A selects one of the nodes D, E or F randomly and send message to it to change its scheduling subset from k2 to k0. The operation of probing mechanism step for this example can be summarized as following:
| Fig. 3: | (a) Before probing mechanism (b) after probing mechanism |
At the end of this step, node D working subset has been changed from k2 to k0 and node A upstream nodes will work in subsets k0, k1, k2. At the end of this step updated working schedule will be broadcasted to immediate neighboring sensor nodes. Although, probing mechanism changes coverage scheduling, it should be perform after nodes know their minimum hop count and neighboring information.
| • | Step 4: Enforce the extra-on rule: Each sensor node decides and updates its extra working subsets to ensure network connectivity in this step. This decision will be based on the extra-on rule and the neighboring information. The update of a sensor node’s working schedule can impact the working schedule of its upstream nodes and the neighboring nodes with the same minimum Hop count to the sink. To minimize the number of broadcast of working schedule updates, it is desirable that a sensor node updates its working schedule after it receives all the latest working schedules from its downstream nodes. This step is also the reverse process of step 1 and starts from nodes with maximum hop count |
RESULTS AND DISCUSSION
Generally a large k value means more number of subsets and thus a subset can wait longer until its next turn to work. If the number of deployed sensor nodes is constant, a larger k value means smaller number of sensor nodes in each subset and, this results in worst network coverage. Proper k or n values are needed so that the energy can be saved with desirable network coverage. Hence, clear definition of the network coverage is needed. The relation between n, k has been represented by Liu et al. (2006) as following:
| (1) |
where, q = r/a, r is the size of the sensing area of each sensor, a is the size of the whole field and t is the network coverage intensity. The ideal value for the network coverage intensity is 1. This ideal value denotes that every point in the field is covered by at least one active sensor node at any given time with the probability of 1. For the coverage intensity 0.9, q = π/400 and k = 5, the minimum number of sensor nodes needed for deployment gotten from (1) is n = 1464.
Here, a MATLAB simulator has been implemented using CSMA/CA MAC layer protocol. Sensor nodes are deployed randomly in a 200x200 m region. The sink node is located at the center of the area. The sensing range of 10 m is assigned for each sensor node. The total number of sensor nodes is selected according to Eq. 1 to meet any network coverage intensity. Because of very light traffic load, packet losses are mainly caused by network partition or channel errors. To prevent packet losses due to broadcast collision or channel errors, a perfect medium channel without medium contention should be adopted. Under each simulation scenario, 100 runs with different random nodes have been executed.
The ratio of extra-on nodes with and without probing mechanism has been shown in Fig. 4. This ratio is defined as the ratio of the number of sensor nodes, which should remain active beyond their assigned working schedule, to the total number of deployed sensor nodes.
| Fig. 4: | Average number of extra-on nodes with and without probing mechanism (pbm) |
In the work performed by Liu et al. (2006), some nodes use nearly shortest path’ to sink and the ratio of extra-on sensor node is around 6.4%. In this research work, all nodes use ‘shortest path’ to the sink node and the ratio of 9.84% has been gotten. As shown in Fig. 4, the ratio of extra-on sensor nodes has been reduced from 9.84% without probing mechanism to 7.78% with probing mechanism for k = 3 and communication/sensing range of 2. The reductions in the ratio of extra-on nodes for k = 3, 4, 5, 6 are 20.93, 19.5, 15.95, 14.5%, respectively at communication/sensing range of 2.
CONCLUSION
In this study we have considered two main requirements of wireless sensor network consist of sensing coverage and network connectivity. Probing mechanism has been implemented in joint scheduling method to include more variety in nodes working schedule and hence reducing number of extra-on nodes. In probing mechanism each sensor node probes its upstream nodes working schedules. If any of upstream nodes not working in nodes working subset, the algorithm searches for repeated subsets. Finally, node sends message to one of the nodes with more repeated subset randomly to change its working schedule to its subset. Simulation has shown that the number of extra-on sensor nodes to ensure connectivity reduced with probing mechanism. The percentage of reduction of extra-on sensor nodes ratio decreases if the number of subsets and consequently number of deployed sensor nodes increases.
ACKNOWLEDGMENTS
This study activity has been conducted in Computer and Network Security Laboratory, University Kebangsaan Malaysia (UKM). The authors would like to thank the University for sponsoring this research through the research university grant UKM-OUP-ICT-36-182/2010.