ABSTRACT

The grouping of sensors is a calculation method for partitioning the wireless sensor network into groups, each group consisting of a collection of sensors. A sensor can be an element of multiple groups. In the present paper, we will show a model to divide the wireless sensor network sensors into groups. These groups could communicate and work together in a cooperative way in order to save the time of routing and energy of WSN. In addition, we will present a way to show how to organize the sensors in groups and provide a combinatorial analysis of some issues related to the performance of the network.

1. Introduction

A wireless sensor network consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, pressure, etc. [1-5]. The sensors cooperate with each other to monitor the targets and send the collected information to the base station [6-8]. Sensors are battery-powered devices having a limited lifetime, restricted sensing range, and narrow communication range [9-11], and densely deployed in harsh environment [12-15]. Organization of sensors in the form of groups is very important, which would facilitate transferring data and routing from one group to another, and it also offers an easy way to analyze the WSN problems such as coverage, localization, connectivity, tracing and data routing [16-20].

2. Sensors Grouping Strategy

A Group of sensors is a collection of overlapped sensors in a single area. Let us define the degree of overloaded sensors by the maximum number of sensors overlapped in the same area, here we denote to the maximum coverage degree of an area by

where where is an area notation called r, are the overlapped sensors, and the number of overlapped sensors. The overlapped sensors that create a degree of an area Create a group of sensors denoted by we call the coverage degree. Figure 1 shows four groups, and. The maximum degree of sensor and senor is that occurs in the area of intersection, which means that there is one and only one area covered by two sensors and that is the maximal overlapping that could be produced, so sensor and create a group of two sensors denoted by. Sake of convenience, we denote to the group of sensors that build up the WSN by

which we call it the mother network group or simply the mother group.

2.1. Counting the Sub-Areas of Sensors Group

Here we start by asking, how many sub-areas are generated if unit disk sensors are partially overlapped? Assuming there is no fully overlapping between sensors, and all sensors are homogenous (sensors have the same sensing range). Say is the function to count the number of sub-areas, definitely., , , (see Figure 2). What is?.

Theorem 1: the sub-areas number of a sensors group

is

(1)

Proof: suppose we have a group of sensors as shown in Figure 3, we can see that the number of areas inside each sensor’s range is seven. Using Top-down approach from to, the number of areas for the top sensor is seven (red areas namely 1, 2, 3, 4, 5, 6, 7). The number of areas inside the sensor’s range are seven, namely (4, 5, 6, 7, 8, 9 10), but the red colored areas, 2, 3, 4, 5, already counted in, so there are only 3 blue colored areas inside sensor’s range, namely 8, 9, 10. For the sensor, it has seven areas inside its sensing range, the 3, 5, 6, 7 are red areas already counted in sensor’s range, the area 10 is blue area already counted in sensor’s range, thus still two black areas in sensor’s range, namely 11, 12. For sensing range of, there are seven areas inside it, three are red areas (4, 5, 6), two are blue areas (9, 10), and one area is black (11), so there is still one area only in (13). Therefore, the number of areas from top to down is 7 + 3 + 2 + 1 = 13. Generally, counting the sub-areas from top to down, the top sensor contains

areas, the second sensor inside the group

contains areas, the third sensor contains areas… the last sensor contains one area. Totally, there are

of areas. Generally, there count of areas is

In addition, we can proof theorem 1 by counting the areas of a group basing on the degree of coverage, if an area covered by k sensors then it called k-covered area. For a group there is only one area is k-covered (the maximum degree of coverage), in the remainder areas, there are k areas are1-covered, k areas are 2-coverd, k areas are 3-coverd… k areas are k-1 covered. Let be the number of areas that j-covered inside a group of sensors. For example, means, there are five areas 1-coverd in. In Figure 4" target="_self"> Figure 4(a), the group of sensors, the number of 1-coverd areas is five. We can count the sum of areas of sensors group as below:

Lemma 1: for sensor range belongs to a group, there are only one area k-covered, k area 1-coverd, k areas are 2-coverd, k areas are 3-coverd… and k areas k-1 covered.

Lemma 2: for a group, all sensors have the same characteristics, for example, the number of areas, the degree of coverage for each area, the number of intersection points located on the border of the sensor, and the number of intersection points located inside sensor’s range.

2.2. Counting the Intersection Points of a Sensors Group

Counting the intersection points of k-overlapped sensors is an easy combination problem. Before proving, here we denote to the number of intersection points by, clearly, , , , ,… then what is the?

Theorem 2: the number of intersection points of sensors group is

(2)

Proof: Assuming that there are k sensors and each sensor has two intersection points with each neighbor sensor, since each sensor has intersection points with others, applying this method to all sensors, we get the total amount of intersection points as. However, while calculating, every single point has been repeatedly counted twice, thus the right answer in regards to the intersection points quantity should be.

We can use top down approach to calculate the number of intersection points, as shown in the Figure 5(a). is the top sensor; is the bottom sensor of the group. The number of intersection points inside (internal) and on the border of sensing range of the top sensor is. In the second node, there are k-2 of intersection points. In the third node, there are k-3 of intersection points. In the fourth node, there are k-4 of intersection points, and there is 0 intersection points in the bottom sensor.

Totally the number of intersection points is

Another method to count the intersection points of a group, we can imagine that the number of intersection points as the number of 2-permutation of k sensors, for example, S is a set of overlapped sensors . The 2-permutation of S is:

,

We can use the Recurrence relation to find the number of intersection points of a group of sensors. We can find the recurrence relation of the number of intersection points as below:

(3)

which can be easily solved using generation function [21]. (See the proof of theorem 3), the solution is , so.

2.3. Counting the Number of Intersection Points That Located within the Sensing Rang of a Sensor Associated to a Group (Internal Points and External Points)

In Figure 5(c), we can see that when k = 3 the number of intersection points located in the black sensor are 5, in Figure 5(b) k = 4, the number of intersection points located in the red sensor are 9, when k = 5 the number of intersection points are 14.

Theorem 3: for a group of sensors, the number of intersection points within the sensing range of sensor is

Proof: it is easy to realize that the number of intersection points (internal and external) of the sensor is satisfying the recursive relation:

(4)

So finding the solution to this recursive relation is the proof of the theorem.

Suppose the generation function is

In addition, suppose that

Then

The external intersection points of sensors are the points located on the border of a sensor. However, the internal points are those points located inside the sensors but not on the border.

Lemma 3 (the number of external points): the number of intersection points located on the border of a sensor, which belongs to a group of sensors is .

Proof: from Figure 5, it is easy to realize that the number of intersection points (external) of the sensor is satisfying the recursive relation:

We can solve this relation using generation function as in the proof of theorem 3. Therefore, the solution to this recursive relation is the proof of this theorem

.

Lemma 4 (the number of internal points): the number of intersection points located inside a sensor (not including the points located on the border) is

Proof: from Figure 5, it is easy to realize that the number of intersection points (internal) of the sensor is satisfying the recursive relation:

(5)

We can solve this relation using generation function as in the proof of theorem 3. Therefore, the solution to this recursive relation is the proof of this theorem.

From lemma 3, and lemma 4, we get the number of intersection points of a sensor that belongs to a group of sensors by counting the intersection points located on the border of the sensor (external points) and the intersection points located inside the sensor (internal points).

(6)

2.4. Counting the Number of Areas within the Sensing Range of a Sensor That Belongs to a Group

Theorem 4: The number of areas inside the sensor that belongs to a group of sensors is

Proof: it is easy to realize that the number of areas inside the sensor is satisfying the recursive relation:

(7)

We can solve this relation using generation function as in the proof of theorem 3. Therefore, the solution to this recursive relation is the proof of this theorem

2.5. Counting the Number of Areas Located within the Sensing Range of a Sensor That Belongs to Multiple Groups

In Figure 1, the network sensors group is:

Our goal is to count the number of areas inside the sensor that associated to multiple groups. The groups to which belongs can be defined as following:

Say that then we can define the mother group of as:

. , where a, b, c are the positive integers numbers that represent the degree of coverage.

As shown in Figure 1 we can define the mother group of sensors, , , , , and as below:

Since only, then the mother group of sensor is

Since, then the mother group of sensor is

Since, then the mother group of sensor is

Since, then the mother group of sensor is

Since, then the mother group of sensor is

Since, then the mother group of sensor is

Since, then the mother group of sensor is

It is clearly that the mother group of sensors of the whole network is equal to the union of mother groups of all sensors as shown below:

Let us now count the number of areas inside a sensor; these areas are generated by intersection of multiple groups of sensors. For facilitate, let us define as the number of areas inside a sensor, which are generated by overlapping of a group of sensors. As explained above, the mother group of is , according to theorem the number of areas which created inside

is (indicated in Figure 6 by numbers 1, 2, 3, 4. The number of areas which are created inside, , is.

The total number of areas inside a sensor, which, associated to multiple groups is denoted by. these areas are created by intersection of sensors belong the mother groups.form the first glance, the seems like

However, this form is not correct, because is an element belongs to every sup-group of this means that there is one area will be counted times. Let us denote the length of mother group by which indicates the number of sub-groups inside the mother group of the sensor. So the corrected count of areas inside, which belongs to, is:

(9)

Below we can count the number of areas of sensors of Figure 7

2.6. Number of Distributed Messages

One of our aims is to find the number of distributed messages that will be generated during communications of sensor associated to mother group. Let us define the number of messages by.For ease, let be the order of. Indicates the number of sensors that belong to every sub-group inside the mother group, but not including, with no repetition, (some sensors might belong to more than one sub-group). For example Figure 1, the order of is; the order of is  

To generalize this idea, we can write the equation further. We have associated to the mother group , the order of mother group of is as the equation below

Here the integer number is the count of subgroups of. In addition, c is the repetition.

It is clear that since the degree of sub-group is one and the there is only one sub-group. Applying this calculation to mother group of sensor , the order.

Theorem 4: The number of distributed messages sent form, associated to a mother group, is

Proof: The number of messages depends on the degree of overlapped sensors. The more the degrees of coverage are, the more the areas will be generated. Therefore, the more messages will be generated. When a target moves within the range of a sensor, it will send notification messages to all neighbors but certainly not to itself. Since the sensor contains a certain number of intersection areas and a certain number of sensors cover these areas, the sensor will send a notification message to all the sensors that cover the same area. is the number of areas inside which belongs to, and is the order of, then

.

The number of messages of the network in Figure 1

3. Conclusion

We had introduced a new method of organizing the sensors of WSN into groups, which would be easy to manage and communicate. This new idea could be applied in coverage algorithms in order to control one node and one target at any given moment, and it could be used to speed up the routing algorithms as well.

4. Acknowledgements

The authors would like to acknowledge The National Natural Science Foundation of China, the National Science Technology Major Project and the China Scholarship Councilfor their supports.

REFERENCES

Distributed messages of network shown in Figure 1.

NOTES

^*This paper is supported by The National Natural Science Foundation of China (NO.61272472, 61232018, 61202404) and the National Science Technology Major Project (NO. 2012ZX10004301-609).