Improved algorithm to configure group number in group management MAC

Abstract

Wireless sensor network becomes crucial with the appearance of the Internet of Things (IoT). IoT roots in the sensors’ data and the technology to transmit the data to the sink. As the importance of IoT arises, the MAC protocols to transmit the data are proposed in many papers. Initially, the sensor devices and the sink remain stationary. As the technology has been advanced, the sensor devices start to move. Accordingly, novel protocols have been proposed for the changing topology. In this paper, we propose Improved-GM-MAC (I-GM-MAC), which means that new algorithms to reconfigure the group number and prevent the endless increasing of group number of the nodes in an isolated area are added to the 3-dimensional group management MAC (3D-GM-MAC).

Keywords

IoT WSN GM-MAC

1 Introduction

Wireless sensor network becomes crucial with the appearance of the Internet of Things (IoT). IoT roots in the sensors’ data and the technology to transmit the data to the sink. The sink is the eventual destination of all the data thus, the data generated from the sensors should be transmitted to the sink with a particular protocol. Also, with WSN, it is possible to collect the data even where people can go directly by deploying sensor devices at where it is unreachable or almost unreachable by people [1].

As the importance of IoT arises, the MAC protocols to transmit the data are proposed in many papers. Initially, the sensor devices and the sink remain stationary. Therefore, the changes in a network topology are only caused by the exhausting battery or the hardware failure, which are called weak mobility [2].

As the technology has been advanced, the sensor devices start to move, not being deployed at fixed locations. For example, smartphones that people are carrying daily life and drones with sensors are the examples of the sensor devices which have mobility. Thus, the protocols proposed for the stationary sensor devices and the sink become inefficient because of the frequent changes in a topology which described as strong mobility [2].

Accordingly, novel protocols have been proposed for the changing topology. Recently, not only sensor devices, but also the sink or sinks get mobility as well so that it causes more frequent changes. To adapt to the changing topology, the nodes which are sensor devices have to be able to self-organize [3].

In this paper, we propose Improved-GM-MAC (I-GM-MAC), which means that new algorithms to reconfigure the group number and prevent the endless increasing of group number of the nodes in an isolated area are added to the 3-dimensional group management MAC (3D-GM-MAC) and the 3-dimensional multi-sink group management MAC (3D-MS-GM-MAC). Also, we apply these algorithms in the 3D-GM-MAC and the 3D-MS-GM-MAC to examine the performance.

The rest of this paper is organized as follow: we provide the related studies in Section 2, describe the proposed research in Section 3 and show the implementation and evaluation in Section 4. The last section, Section 5, discusses the conclusion.

2 Related studies

One of the advantages when using the WSN is that the sensors can be deployed at unreachable places by a human. Even if they are not deployed at the place which is impossible to reach by a human, it is hard to replace the sensors frequently. However, because the sensors have the limited battery, maximizing the efficiency is crucial in WSN. Also, not only maximizing the efficiency of each sensor but also maximizing the lifespan of a network is important. If few nodes are left after the others are dead, it is not meaningful as a network because the data cannot be collected to the sink [4].

Therefore, a lot of MAC protocols are proposed to improve the efficiency. The MAC protocols are typically divided into two types, which are called scheduling based and contention based. These two types are divided by the strategy of wireless media access.

The scheduling-based protocol is a type of protocols that make the node be able to communicate by scheduling. This scheduling-based protocol is divided into some categories, which are traffic-based, clustering-based, priority-based, and time-division multiple access (TDMA) MAC protocol.

For example, low energy adaptive clustering head (LEACH) protocol [5] is one of the scheduling-based protocol, especially the clustering-based protocol. It elects cluster heads among the nodes and creates each cluster in set-up phase. Then, the cluster heads collect the data from the nodes and send the collected data to the sink in steady-state phase.

On the other hand, contention-based MAC protocol makes the nodes contend to access the media. However, because of the idle state, the node lose their energy with doing nothing [6]. This is a critical problem when it comes to the WSN. So, some protocols, which is based on contention-based protocols but have some differences, are proposed. Sensor-MAC (S-MAC) [7] and Timeout-MAC (T-MAC) [8] are the examples. S-MAC makes sleep and active mode to reduce the energy for idle listening state. T-MAC is an enhanced version of S-MAC and it adapts the dynamic duty cycle to dynamically end the active mode.

However, these are the early protocols for WSN. The feature of these protocols is that they are designed for the static environment. In other words, these protocols are designed for the topology with the weak mobility. Therefore, if the sensor nodes and the sinks have each mobility, these protocols are not suitable. In former times, the sensors and the sink are stationary. However, as the technology has advanced, it becomes possible to have physical movements for the sensors and the sink. For instance, smartphones have many sensors such as GPS or temperature sensor and are carried by people. Also, there are a lot of things used as a mobile sensor or sink such as drone, vehicle, passengers and etc.

Group management MAC (GM-MAC) protocols [9] is a protocol for the environment with the mobile sensors. GM-MAC protocol is a protocol which is rooted in Timeout-MAC (T-MAC). It groups the sensor nodes by the distance between the sink and each node. The sink’s group number is 0, and the group number increases from the sink. That is to say, the bigger the group number is. A node only transmits its data to the upper group node whose group number is one less than its group number. Provided that the data are generated the sensor with the group number N, the data is going to transmit to the sink across nodes with group numbers n through 1.

Because the sensor nodes have mobility, the topology changes. At a certain point, a node cannot transmit its data to the upper group node which is configured previously. No Clear-to-Send (CTS) packet to 3 Request-to-Send (RTS) packets is defined that the data cannot be transmitted. Therefore, to transmit the data, the node needs to reconfigure its group number and the upper group node where the node transmit its data.

If a node receives from another node whose group number is n and its group number is not configured or bigger than n, it configures its group number as n+1. The Fig. 1 shows the structure of GM-MAC.

Fig. 1

Structure of GM-MAC.

Because the real world is 3-dimensional, 3D-GM-MAC [10] is proposed as an enhanced version of GM-MAC. The experiment is based on 3-dimensional environment. Also, it proposes new algorithm to configure group number and the formula to calculate the buffer threshold.

Because of the stability problem mentioned at the explanation of GM-MAC, it proposes the new algorithm to configure group number. According to the reconfiguring group number algorithm of GM-MAC, a node always has the smallest group number as far as it can transmit the data.

In 3-dimensional GM-MAC (3D-GM-MAC), a node does not choose the smallest one, but it collects the group number from the neighbors and calculates the group number. Because the group numbers from neighbors and the weights based on the volume are considered, it is more stable than the way of GM-MAC. The formula for calculating a group number is as Fig. 2.

Fig. 2

Formula for calculating a group number.

Also, the buffer threshold of a node is differed by the node’s group number. Considering the volume, the smaller the group number is, the less the number of the nodes located in that group is. So if all the nodes have same buffer threshold, it probably causes the bottleneck phenomenon. So, 3D-GM-MAC applies a formula to set the buffer threshold of a node by its group number. The formula is as the Fig. 3.

Fig. 3

Formula for setting buffer threshold.

3-dimensional multi-sink GM-MAC (3D-MS-GM-MAC) [11] is an enhanced version of 3D-GM-MAC. It proposes a way to extend 3D-GM-MAC to the environment for multiple sinks. If 3D-GM-MAC is used in large area, the maximum group number is bigger than expected. If data are generated from the edge of the area, the data are going to be transmitted to the sink through the considerable number of nodes. Because the data should be transmitted many times through the all nodes which have the group number N to 1. It causes the waste of energy. However, multiple sinks can solve this problem. Having multiple sinks, the distance between each node and one sink will be shortened. Furthermore, the load of data can be distributed. Thus, the method to expand the protocol to use the multiple sinks is needed.

3D-MS-GM-MAC is proposed with the algorithm to do the initial setting for the sinks and the sensor nodes and the algorithm to reconfigure a new group number when a node cannot transmit its data. In initial setting, the group number and sink number of each sensor are set. After initial setting, if a node cannot transmit its data to the upper group node, it try to reconfigure its group number again. Same as GM-MAC and 3D-GM-MAC, it judges the impossible of data transmitting by no CTS packet even after 3 RTS packets. Because there are multiple sinks in 3D-MS-GM-MAC, the configuration of the nodes which are moving around the boundary of each sink is very important. It gives the threshold K to prevent frequent changes of sink number when a node is moving from a sink to another sink. The node changes its sink number after it recognizes that the difference between the group number based on the previous sink and the one based on the new sink is more than K.

However, it still uses the formula proposed in GM-MAC for calculating new group number and configuring the buffer threshold which is differed by the node’s group number.

3 Proposed research

In GM-MAC and 3D-GM-MAC, the condition that a node judges the possibility of transmitting of the data is same. No CTS even after 3 RTSs, is defined that it cannot transmit the data and the node sends hello packet to its neighbor to figure out its new group number. After receiving all the reply packets from the neighbors, it calculates the new group number and updates its information as the result so that it can participate in the transmission of data again.

However, this algorithm has a problem. The problem is a continuous increment of group number when a node is deployed in an isolated area, which means the node cannot transmit its data to the sink eventually.

Suppose that there are two nodes, node A and B. The node A has the group number n, and the node B has the group number n+1. Also, the node A is the parent of the node B. Thus the node B transmits its data to the node A, the node A sends its data to its parent and so on. Eventually, all the data are gathered at the sink.

After a while, the connection between the node A and its parent is lost. The node A sends the hello packets to the neighbors. Unfortunately, there is only one neighbor, the node B. The node B sends the reply packet back to the node A. The reply packet contains the information which is the group number of the node B, n+1. Because the node A only has one neighbor, the node B, it sets the node B as its parent node. That means the node A has the group number n+2. So now, the node B loses its parent node. As the node A has the group number n+2, the node B cannot transmit its data to the upper group node. Therefore, the same situation above which happened to the node A occurs to the node B again and this happens repeatedly.

The fundamental problem is that the nodes in the isolated area do not know that they cannot realize that they are located in the isolated area by themselves. They only know that if they can transmit the data to the parent node in the upper group. Therefore, the way to resolve this problem is to make the node to recognize if they are located in the isolated area. In I-GM-MAC, the periodical packet from the sink, which called a check packet, resolves this problem.

First, the sink generates check packets which have the information of the group number 0 periodically. The period is determined by the developer. The nodes which have the group number 1 receive the check packets, change the information of group number as 1, send to its neighbors. This process is repeated continuously and finally, every node which can send its data to the sink receives the check packet.

In other words, if a node cannot receive any check packets from its parent node during the time period, it can realize that its data cannot be transmitted to the sink because it is located in an isolated area. Because it cannot transmit its data to the sink, it sleeps until it receives the check packet which means it is connected to the sink again. The Fig. 4. Shows the transmission of check packets from the sink to the nodes. Also, it shows that the nodes in the isolated area, which are the node x and the node y, cannot receive the check packets from the sink.

Fig. 4

Transmission of check packets from the sink to the nodes.

Also, another problem is found in 3D-GM-MAC. In order to make the topology stable, 3D-GM-MAC proposes a formula to calculate each group node’s group number. However, under certain circumstances, this formula gives a group number which makes the node cannot transmit its data even though it has the neighbor that it can transmit its data. One of these circumstances is as Fig. 5.

Fig. 5

Example of the group number which makes the node F cannot transmit its data.

This can be considered as a waste of energy because the node F in the Fig. 5 keep going through the procedure of reconfiguring even though it is possible to transmit its data. Therefore, to prevent this situation, another checking process need to be added in the way of calculating the new group number in 3D-GM-MAC. The logic is as below. If a node cannot transmit its data to the parent node, send hello packets and receives reply packets from all the neighbors. Calculate the new group number with the formula which is proposed for reconfiguring in 3D-GM-MAC and check if it is possible to transmit its data to the upper group node with the calculated group number. If it is possible, configure the group number as the result of calculating and if not, configure the group number as one more than the smallest group number amongst the group numbers of reply packets. The Fig. 6 shows the flowchart of reconfiguring a new group number when a node cannot transmit its data to the upper group node. The formulas that are given in the flowchart are in the Fig. 2, which are proposed in 3D-GM-MAC.

Fig. 6

Flowchart of reconfiguring a new group number.

4 Implementation and evaluation

The simulation is implemented with C++ on Visual Studio 2015. The simulation environment is as below

Table 1
Simulation environment

Factor Setting Value

Area 300 m * 300 m * 300 m

The number of sink 1

The number of sensor node 100

Sensor node CC2420 radio transceiver from Texas Instrument

Initial energy of sensor node 3000 mW

Energy when sensor node sends data 52.2 mW

Energy when sensor node receives data 56.4 mW

Energy when sensor node is idle 56.4 mW

Buffer size of sensor node 200 Byte

Maximum distance that sensor node can communicate 90 m (application distance of ZIGBEE)

Data generation Average 1 time per 1 min (following Poisson distribution)

Maximum speed of sensor node 5 m/min

Pattern of sensor node’s movement random

Factor	Setting Value
Area	300 m * 300 m * 300 m
The number of sink	1
The number of sensor node	100
Sensor node	CC2420 radio transceiver from Texas Instrument
Initial energy of sensor node	3000 mW
Energy when sensor node sends data	52.2 mW
Energy when sensor node receives data	56.4 mW
Energy when sensor node is idle	56.4 mW
Buffer size of sensor node	200 Byte
Maximum distance that sensor node can communicate	90 m (application distance of ZIGBEE)
Data generation	Average 1 time per 1 min (following Poisson distribution)
Maximum speed of sensor node	5 m/min
Pattern of sensor node’s movement	random

To examine the proposed I-GM-MAC, we compare the energy of each node in 3D-GM-MAC and I-GM-MAC.

Figure 7 shows the locations of the nodes after initial setting with the single sink. This is the initial locations of the nodes in experiment for 3D-GM-MAC and I-GM-MAC. The black circle in the middle is the sink, and the blue, green, pink and red circles mean the nodes with the group number 1, 2, 3 and over than 4 respectively.

Fig. 7

Initial locations of the nodes in experiment for 3D-GM-MAC and I-GM-MAC.

Figures 8 and 9 show the energy of each sensor node in 3D-GM-MAC and I-GM-MAC when the size of data is 10 bytes. The red lines show the number of live nodes. In 3D-GM-MAC, most of the sensor nodes are dead after 1035 days. However, all the sensor nodes are still alive after 1035 days in I-GM-MAC. This is because that the I-GM-MAC saves the energy to try to reconfigure its group number in 3D-GM-MAC.

Fig. 8

The energy of sensor nodes in 3D-GM-MAC when the size of data is 10 bytes.

Fig. 9

The energy of sensor nodes in I-GM-MAC when the size of data is 10 bytes.

Also, the Figs. 10 and 11 show the energy of each sensor node in 3D-GM-MAC and I-GM-MAC when the size of data is 100 bytes. The starting points to run out of battery are similar. However, in I-GM-MAC, some nodes are still working longer than the nodes in 3D-GM-MAC.

Fig. 10

The energy of sensor nodes in 3D-GM-MAC when the size of data is 100 bytes.

Fig. 11

The energy of sensor nodes in I-GM-MAC when the size of data is 100 bytes.

This is because that the algorithms applied in I-GM-MAC configures the group number that makes the node to transmit its data certainly if there is another node which is able to be the parent. By contrast, the 3D-GM-MAC sometimes configures the wrong group number that makes the node cannot transmit its data even if there is another node which can be the parent. By configuring the right group number, the node doesn’t need to try to reconfigure next time. So the energy to process of reconfiguring the group number is saved in I-GM-MAC. To be specific, not only the energy of the node to send hello packets and receive reply packets from the neighbors, but also the energy of the neighbors to receive the hello packet and send the reply packet can be saved. As the result, the nodes are alive longer than the 3D-GM-MAC.

The reason why the results with 10 bytes data show the big differences than the ones with 100 bytes is that the working days are longer with 10 bytes data. Because the energy to transmit 10 bytes data is smaller than the one to transmit 100 bytes data, the experiment with 10 bytes consumes the energy more slowly. That make the nodes work longer and as the days get longer, the time to move around the area gets longer too. Therefore, the number of reconfiguring the group number gets bigger and that shows thebigger differences between the result in 3D-GM-MAC and I-GM-MAC.

5 Conclusion

In this paper, we proposed the I-GM-MAC which contain the new algorithms to prevent the increment of group number in an isolated area and the configuration of group number with wrong group number in 3D-GM MAC. The results shows that it is more efficient compared to 3D-GM-MAC.

Likewise, the 3D-MS-GM-MAC is also following the basic algorithm of 3D-GM-MAC. Therefore, the same problems of continuous increasing group number of the nodes in an isolated area and reconfiguring wrong group number are found in 3D-MS-GM-MAC as well.

In future works, we are going to apply these algorithms to the 3D-MS-GM-MAC to expand to network with the multiple sinks and compare the results.

References

Dargie

, Poellabauer

, Fundamentals of Wireless Sensor Network: Theory and Practive, Wiley Publishing, 2010.

Ali

, Suleman

and Uzmi

Z.A.

, MMAC: A mobility-adaptive, collision-free mac protocol for wireless sensor netowkrs, 24th IEEE International Performance, Computing, and Communications Conference, 2005, pp. 401–407.

Sohrabi

, Gao

, Ailawadhi

and Pottie

G.J.

, Protocols for self-organization of a wireless sensor network, IEEE Personal Communicationsl7(5) (2000), 16–27.

Akyildiz

I.F.

, Su

, Sankarasubramaniam

and Cayirci

, Survey on sensor networks, IEEE Communications Magazine40 (2002), 102–114.

Handy

M.J.

, Haase

and Timmermann

, Low energy adaptive clustering hierarchy with deterministic cluster-head selection, Fourth IEEE Conference on Mobile and Wireless Communications Networks, Sweden, 2002, pp. 368–372.

Song

W.-M.

, Liu

Y.-M.

and Zhang

S.-E.

, Research on SMAC protocol for WSN, IEEE Wireless Communications, Networking and Mobile Computing, WiCOM’08 4th International Comference on, China, 2008, 1–4.

, Heidemann

and Estrin

, An energy-efficient mac protocol for wireless sensor networks, IEEE Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings, Vol. 3, 2002, pp. 1567–1576.

van Dam

and Langendoen

, An adaptive energy-efficient mac protocol for wireless sensor networks, in Proc of the 1st International Conference on Embedded Networked Sensor Systems2003, pp. 171–180.

Kim

, et al., Energy efficient MAC scheme for wireless sensor networks with high-dimensional data aggregate, Mathematical Problems in Engineering 2015, 2015.

10.

Ryoo

, Sun

, Lee

and Kim

, A 3-dimensional group management MAC scheme for mobile IoT devices in wireless sensor networks, Journal of Ambient Intelligence and Humanized Computing (2017), 1–12.

11.

Shin

, Hong

B.I.

and Ryoo

, Dimensional Group Management MAC Scheme for Wireless Sensor Devices with Mobile Multi-Sinks, International Conference on Green and Human Information Technology, 2018.