Improved Uneven Cluster-Based routing protocol based on CRT algorithm

Abstract

Energy-Efficient Uneven Clustering (EEUC) protocol is applied to low-redundancy Wireless Sensor Network (WSN), the uneven consumption of sensor node energy leads to nodes’ early death which will seriously affect the network quality. This paper proposes the Chinese Remainder Theorem (CRT) division algorithm for EEUC Energy-Efficient Uneven Clustering routing protocol optimization. The nodes split the packets before forwarding and balance the energy consumption of the nodes forward packets which results in alleviating hot problems of wireless sensor networks. We also add energy and distance parameters to the threshold function in the cluster heads selection mechanism, and optimize the cluster semidiameter to make the cluster head election distribution more reasonable which will help to optimize the network energy consumption. The result of simulation indicates that the algorithm we propose can make energy consumption of lower redundant sensor network nodes more balanced and delay the first death time of node as well as prolong the network life time effectively.

Keywords

LEACH protocol Uneven Cluster-Based energy balance competitive cluster radius low redundancy

1 Introduction

Wireless sensor networks (WSN) is a self-organizing network system consists of a large number of sensor nodes randomly deployed in the monitoring area by the way of wireless communication [1], In this paper, low redundancy sensor networks is used in industrial production, each sensor node bears higher costs and the corresponding data acquisition task. There are nearly no redundant nodes, so some key data can not be collected when node death occurs, and lead to the end of network’s effective life [2].

Many scholars have done a lot of research work for energy-balance problem of sensor networks. Heinzelman presented typical clustering algorithm, that is LEACH clustering routing protocols [4], whose main idea is based on “wheel”. The sensor nodes are based on cluster units and send data to Sink node by cluster head node. Because of the number and location randomness of cluster head nodes, some of the cluster head nodes always incurred excessive energy consumption, then uneven energy consumption leads to node premature death phenomenon. Li Chengfa proposes LEACH algorithm based on unbalanced energy issue, that is the uneven clustering EEUC routing protocol [5]. He introduces competition cluster radius in the cluster head election, and the distance between the head node and Sink node cluster head node is added as a parameter to the selection mechanism, to make the cluster head distribution more reasonable. At the same time, his algorithm replaces the single-hop transmission with multi-hop transmission between cluster head node and sink node, which greatly improves network energy consumption of LEACH protocol, but cluster head nodes closed to Sink node not only bear data collection and sending in the cluster, but also transfer remote cluster data, so the energy consumption is large and will lead to premature aging of some individual cluster head nodes. Tang Jiashan proposes I-EEUC protocol [6] to improve EEUC, the algorithm chooses nodes’ residual energy and data of the members of the cluster as reference factors for the cluster head node selection policy of hop, it can select more appropriate node as a relay node for transmission and extend node death time. Giuseppe Campobello proposes CRT-Based Packet-Forwarding algorithm [7], in which ordinary nodes of the energy-isomorphic network use CRT-Based to split data packets, then transmit them to the Sink node via layer. The algorithm improves the “funnel effect” of nodes which are near the network and effectively balance the energy consumption of network nodes. However, the algorithm is based on planar-type network, in which there is no management node, also it lacks optimization to management communication resources and it has poor network scalability, so it is unable to adapt to a low redundancy network of industrial applications. Therefore, in order to adapt to application scenarios, the CRT algorithm is applied to a hierarchical network to enhance their adaptability and topology.

For low redundancy wireless sensor network model, the emergence of node death means the end of effective life time of network. This paper considers energy-balancing problem of sensor nodes in low redundancy network model, so CRT algorithm is applied to the data transfer process of EEUC uneven clustering routing protocol, it uses Chinese Remainder Theorem to split data packets for multi-hop transmission. The algorithm can not only balance energy consumption distribution of data transmission is more uniform and effectively mitigate premature aging phenomenon of some individual node, but also delay the first death time of a node and extend the effective life time of the network.

2 Algorithm design

Suppose there are N nodes which are randomly distributed in m*m network, then Sink node is located in the middle of the network and the network is a homogeneous network, also Sink node is set to unlimited energy and energy of each remaining node is the same.

2.1 Hierarchical network initialization

The main purpose is to pre-allocate the network layout in the initialization phase. After the random deployment of nodes, firstly establish a hierarchical structure of the network according to the node covering hierarchical model.

As shown in Fig. 1 sensing radius of each node is R, then the coverage area of sensor node is πR², the communication coverage area of the sensor nodes is as follows: D = D_Sink ∪ D_A ∪ D_B ∪ D_C ∪ D_D … ∪ D_i. Where in, D_i represents the sensing area of sensor nodes. Node A, B are within the sensing coverage of sink node, and the remaining nodes adopt a multi-hop manner to send data to the sink node. Neighbor nodes set of sink node is sink: {A, B}, neighboring nodes set of node A is A : {Sink, D, C}, and so on, neighboring nodes set of each node are B : {Sink, E, F}, C : {A, D, E, H}, D : {A, C, H}, E : {C, B, F, G}, F : {B, E, G}, H : {C, D, E}, G : {C, E, F}.

Fig.1

Network coverage area graph.

As shown in Fig. 2, hierarchical model is established on the sensing area, and sink node is chosen as the center to divide network into several layers. During data transmission process, there are no data transfer and transmission between the nodes in the same layer of network, but node in outer layer will choose the node of upper network as relay node to send data. relay node of H node is {D, C, E}, relay nodes of other nodes are G → {C, E, F}, F → {B}, E → {B}, D → {A}, C → {A}, A → {Sink}, B → {Sink}.

Fig.2

Hierarchical network graph.

According to the network Hierarchical model, the nodes broadcast initialization message (IM) via the broadcast mechanism, also establish information table and complete transmission path planning, as shown in Fig. 3

Fig.3

Network initialization IM information exchange graph.

Step 1: Determine layer number (Layer) through initial information (IMs) exchange and add labele SN = 1, then ensure each node is covered, at last, broadcast IM: [Layer = 1] from the sink node.

Step 2: Set the threshold value (TD MAX) based on the sensing radius R. If the node receives the broadcast of sink node and the distance to the sink node d (Si, Sink) ≤ TD_MAX. Then it is marked as Layer = 2, which means nodes belong to the second layer, while mark SN = 0. Layer = 2 node uses clustered single hop communication mode to communicate with sink node, while the nodes of this layer broadcast IM message: [Layer = 2, ID], the nodes of the same level does not receive broadcast information of each other.

Step 3: The nodes of second layer broadcast IM information within a broadcast radius (broadcast distance). The sink nodes of first layer also receive broadcast information, those are their downstream node ID, and update their information table. Nodes of the third layer (Layer = 3) receive IM information of neighboring nodes in upper layer to update their information table and transfer IM. At this time, node initialization broadcast messages IM of second layer are updated as: [Layer = 2, {Layer = 1node ID set}, their own ID, {Layer = 3node ID set}], and their own mark SN = 0. Nodes’ IM information table will be used in the later data transfer phase.

Step 4: Repeat Step2 ∼ Step3 and promote to the whole network. Each node will build their own information table based on received IM, then the upstream node and downstream nodes can be got by querying the information table. In the data transfer process, select and calculate the appropriate relay node through existing information table, then tansfer data packets, and calculate the splitting number of data packets based on the number of relay nodes in information table until all SN marks of nodes in the network are 0.

2.2 EEUC uneven clustering algorithm improvement

EEUC algorithm improves the network energy imbalance problem of leach protocol, the main idea is to introduce competition cluster radius, nodes within the radius have no competition qualify to become cluster head, but EEUC uses threshold T(n) of LEACH protocol. Although the probability of node becoming cluster head does not changed, the competitive cluster radius will make the cluster head nodes less than the expected p.

So, in the cluster head election mechanism, the threshold has been improved [8]:

$T (n) = {\begin{matrix} \frac{p}{1 - p * [rmod (1 / p)]} [θ \frac{E_{i}}{E_{init}} + (1 - θ) \\ \frac{D_{i}}{D_{\max 2 BS}}], n \in G \\ 0, n \notin G \end{matrix}$ (1)

Wherein, E_i is the current residual energy of the node, E_init is the initialization energy of the node, D_i is the distance between the node and sink node, D_maxsBS is the maximum of distances between all nodes and the sink node. θ is a weighting factor of energy and distance [9]. G is node set that includes nodes haven’t been elected as cluster head, p is the desired cluster head node’s percentage in the total number of nodes.

Improved threshold increases probability of sensor nodes near sink node becoming cluster head, also increases the probability of nodes with greater energy becoming cluster head node, then can get ideal network topology. In the area closed to sink node, clusters are smaller, while the number of clusters should be more than distant areas. Increasing the number of cluster heads in area near sink node can help ease larger energy load issues of nodes near the cluster head, then optimize the layout of the cluster head nodes in a non-uniform clustering network. At the same time can achieve a balanced distribution of energy loss and relatively balance the network load.

In clustering stage, EEUC algorithm uses non-uniform competitive cluster radius:

$R_{c} = (1 - c \frac{d_{\max} - d (s, BS)}{d_{\max} - d_{\min}}) * R_{c}^{0}$ (2)

Range of competition radius is: $2 / 3 R_{c}^{0} \sim R_{c}^{0}$ , the distance between the cluster heads is 2/3d₀ ∼ d₀, if the competition radius R_c is too large, the communication distance between cluster head nodes will be too far. Also it makes number of selected cluster head nodes less than the expected total number of nodes percentage p in the cluster head node within the area with specified node scattered, resulting in too large data transfer amount of cluster head node and the premature death of cluster head nodes.

The improvement of competitive cluster radius [10]:

$R_{c} = (1 / 2) * (1 - c \frac{d_{\max} - d (s, BS)}{d_{\max} - d_{\min}}) * R_{c}^{0}$ (3)

Where d_max and d_min represent maximum and minimum distance between nodes and aggregation nodes in the network, d (s_i, DS) represents Euclidean distance between the node s_i and sink node, $R_{c}^{0}$ represents the greatest competitive radius of candidate cluster heads. The relationship between competition radius and sink node to node distance decreases linearly. When C = 1/3, range of competition radius is: $(1 / 3) R_{c}^{0} \sim (1 / 2) R_{c}^{0}$ , the spacing between the cluster heads that reducing to (2/3) d₀ ∼ d₀ is relatively reasonable.

2.3 Cluster head splitting packets

Divide data packets [12, 13] according to the Chinese Remainder Theorem (CRT) [11]. Sensing data packet that the network node sends is m, packet size is w, the range of data packet is 0 ∼ 2^w - 1. At the same time, select a set of prime numbers {p₁, p₂, …, p_i}, where p_i > 1, m_i is the sequential modulo arithmetic of prime number on array primes data packet m, such as the formula:

$\begin{matrix} m_{i} & = & mmod (p_{i}), p \in {p_{1}, p_{2}, \dots, p_{i}}, \\ i \in {1, \dots, N} \end{matrix}$ (4)

The resulting remainder is m_i, i ∈ {1, …, N} is the remainder packet of splitting calculation, remainder packet m_i will replace data packet m to do the data transmission.

The length of split packet m_i determines the energy consumption of the entire network, and fewer number of bits of packet transfer will result in higher network energy efficiency. in order to ensure the length of data packet that is split by prime array is minimum, it is necessary to select a minimum set of prime numbers to meet the conditions, so continuous prime set satisfies the formula (5):

$M = Π_{i} p_{i} \geq 2^{w}$ (5)

The node gets the remainder data packet number N < = N_max by the relay node number N of IM information. The index table query points the Minimum Prim Set (MPS) node, and then uses each number of prime number array to successively do modulo operation on packets m and splits them into a number of N remainder packets.

Assume packet length is w = 48 bit, acquire the packet splitting number N ≥ 4 by querying IM information, and it should satisfy the conditions N < = N_max, that is, then get a group of prime numbers {4091, 4093, 4099, 4011}. The group calculated the product of prime numbers M = 4091 * 4093 * 4099 * 4111, the prime numbers to meet the conditions set, at the same time to meet the conditions of the minimum set of consecutive prime numbers is {4091, 4093, 4099, 4011}. Calculate the product of prime numbers group M = 4091 * 4093 * 4099 * 4111 ≥ 2⁴⁸, the prime numbers group meets the conditions M ≥ 2^w, at the same time, the minimum consecutive prime numbers set that meets the conditions is {4091, 4093, 4099, 4011}.

Each sensor node stores a prime number list and possesses an index list that can make it quick and easy to obtain prime array by querying. When a node is splitting data, according to a given data packet length w and the remainder packet number N, prime number array can be quickly obtained by querying the index table. As shown in Fig. 5, the prime number array {4091, 4093, 4099, 4011} can be got through the packet length w = 48 bit and the remainder packet number N = 4; When the packet length w = 48 bit and remainder packet number N = 3, the prime array is {65537, 65539, 65543}.

Fig.4

Uneven clustering algorithm.

Fig.5

Prime list.

2.4 Cluster head forward packets

Common nodes collect data and upload the data to the cluster head nodes, then cluster head nodes compute the distance between themselves and the relay nodes. If the distance between cluster head node and sink node is lower than the threshold value TD_MAX, the cluster head node changes to directly send data packets to sink node, without through the relay node. If the distance between cluster head node and Sink node is higher than the threshold value TD_MAX, the cluster head node transfer data packets according to CRT splitting algorithm. Figure 6 shows the process of cluster head node transferring data packets m via the relay node: transfers the packets to the relay node {C, D, E, F} by way of broadcasting, lastly, the relay node selects the appropriate primes packets to split according to the splitting number of data packet division. After the relay node receives a packet, obtain the parameters by established IM information table, then split the received data pockets by the queried smallest prime number array (MPS). Use the prime number to do remainder calculation on raw packets m, and get the remainder data packet {m₁, m₂, m₃, m₄}, the relay nodes {C, D, E, F} replace packet m with the remainder packet m_i, then send data packet to the next hop node.

Fig.6

Cluster head transferring splitting packets.

In order to rebuild the message, relay node need to install packet header in the split packet data. Sink node gets division number of data packets by the number of bits of packet header, and get the qualifying of this packet. The first bit of header is marked as 1, so n bits data represents the n - 1 split packets, at the same time, the header is read with shift operation, when the first bit is 1, the packet m_i is numbered as i = n.

3 Outlined algorithm implementation process

Improved uneven cluster-based routing protocol based on CRT Algorithm process, detailed description is as follows:

Network initialization

Step1: Start from Sink node to broadcast IM information layer by layer

If A node is within the broadcast range of the node and is not the same layer node This node will write the ID of broadcast node into IM message

end If

Step2: Verify all nodes tag information SN = 0, then the broadcast is completed

Step3: node setup information table and prime number table according to IM

Polling phase, superposition of the number of rounds r

A. cluster building phase

Step4: The base station initializes threshold T (n) and adds energy and distance parameters

Step5: Each node compares its own random value with the threshold T (n)

If random (0, 1) < = T (n)

The sensor node is elected as cluster head (CH)

Calculate the cluster competition radius (Reoc) of this cluster head node

If Reoc ≤ distance from the node to the cluster head node

The cluster node is not eligible to run for the head node

end If

Step6: cluster head node broadcasts message CH-ADV-MSG;

Step7: ordinary nodes receive broadcast information and calculate the communication distance, then send join message (JOIN-MSG) to CH to added to inform cluster head to join the cluster

B. Data transfer phase

Step8: ordinary nodes collect data packets DATA-MSG

Step9: CH nodes integrate data packets uploaded by all member nodes to form data packets m

If the distance (CHi, Sink) < = TD_MAX

Step10: CH nodes send data packet m to Sink node

Otherwise CH node to send data to Sink node by multi-hop data transmission, then conduct Step11;

Step11: CH nodes query IMEI information table to get IDs of i_max relay nodes, then query the remaining energy of the relay node and remove the relay node with minimum remaining energy, next send data packets m to relay nodes.

Step12: Relay node receives data packet m_i, then it queries IM information to obtain component number i and splitting number i_max, then search prime numbers p_i through prime numbers indexing table, finally generate remainder packets m_i by taking the remainder of m

Step13: Select node with the minimum node-link energy cost in the next layer as relay node.

C. Sink nodes reorganize remainder packets

Step14: Sink node receives data packet m_i, determine whether all the packets are received by component number i and the splitting number i_max. It sorts the remainder packets to find quality array. Then makes prime numbers corresponding with the remainder packets m_i one by one, uses Chinese Remainder Theorem to reorganize packets and obtain contents of the original packets m.

4 Simulation

Simulate the improved protocol in Matlab, compare it with EEUC protocol and I-EEUC protocol to evaluate performance of the proposed agreement. Parameters setting of simulation environment are given in Table 1.

Table 1
Simulation parameters set

Parameter Value

Nodes 200

Network Size 200 m×200 m

Base Station Coordinates (100,100)

Packet Size 48 bit

Capability of Initial Node 0.003 J

Probability of Desired Cluster Head Node 0.1

Simulation Rounds 50

R_c 80

E_elec 50 nJ(bm)^-1

ɛ _fs 10 pJ(bm²)^-1

ɛ _mp 0.0013 pJ(bm⁴)^-1

Parameter	Value
Nodes	200
Network Size	200 m×200 m
Base Station Coordinates	(100,100)
Packet Size	48 bit
Capability of Initial Node	0.003 J
Probability of Desired Cluster Head Node	0.1
Simulation Rounds	50
R_c	80
E_elec	50 nJ(bm)^-1
ɛ _fs	10 pJ(bm²)^-1
ɛ _mp	0.0013 pJ(bm⁴)^-1

Figure 7 is distribution location of cluster head nodes a network round, nodes are randomly distributed in 200 * 200 network layout. The current round selects out of the 11 cluster head nodes, and red circle represents the competition radius of the cluster head node. After a node is selected as cluster head, other nodes in its competition are not eligible to compete for cluster head. Meanwhile, because of the optimization of the uneven clustering algorithm, most cluster head nodes are nearby Sink nodes. So improved algorithm can make distribution of cluster head nodes more reasonable.

Fig.7

Distribution of cluster head nodes.

Figure 8 shows the data transmission path that cluster head nodes transfer data in a certain round. Considering web energy balance, quit to choose the cluster head nodes with minimum remaining energy E as a forwarding node. When transfering data, cluster head nodes which are far from the Sink node select a set of nodes as a relay nodes to transfer packets. cluster head nodes which are near the Sink node send the data directly to Sink node.

Fig.8

Transfer path of cluster head nod.

Ordinate in Fig. 9 shows remaining energy of cluster head node in a round, abscissa is the number of nodes. The problem on the distribution of cluster head nodes can be seen: numbered 48,140 cluster head node carries more data transfer burden, which results in energy consumption is far greater than other cluster head nodes, also energy consumption of nodes in I-EEUC algorithm is relatively more fluctuate.

Fig.9

Head node cluster energy consumption of a round.

This article improves the data transfer mechanism, the energy consumption of cluster head nodes is relatively balanced, and divide the energy that is used to transfer data to each cluster head node, so energy consumption of a certain node may not be larger than the other cluster head nodes, that means it reduces the premature death probability of an individual cluster head node and balances the energy consumption of the entire network.

Ordinate of Fig. 10 is the number of surviving network nodes, the abscissa is the current number of round.

Fig.10

Number of surviving nodes.

It can be found that the nodes are all surviving nodes in the initial stage of network, and the total number of nodes is 200, in 4th round, the EEUC protocol running network appears case of node death, but the I-EEUC protocol running network firstly appears node death in 11st round. In the improved algorithm of this article, the node death firstly appears in the 14th round. Meanwhile, the death rate of network node is very low before 80th round, the mortality rate increases after the 80 rounds. This is because the algorithm balances the energy consumption, so that most nodes die at a very late time. Thus, our algorithm can effectively prolong the death time of nodes, and make a contribution to the energy balance of the entire network.

5 Conclusions

To solve the unbalanced energy consumption issue of EEUC uneven cluster head node clustering algorithm, this paper introduces CRT packet splitting algorithm, and improves energy balance issue during the data transfer process, effectively alleviate the “hot” nodes energy consumption issue. Simulation shows that the algorithm of this paper has improved cluster head selection mechanism in the cluster head node layout issues, as well as energy-balancing issue of data transfer mechanism. The proposed algorithm effectively extends the life of the network, has been network layout with more uniformly distributed cluster head nodes.

Footnotes

Acknowledgments

S. sun and S. chen’s work were supported by the Key Laboratory of Advanced Process Control for Light Industry (Ministry of Education) and the Fundamental Research Funds for the Central Universities, No. JUSRP11560, National Science Foundation of China (Project Nos. 21206053 and 21276111) and the Enterprise university-research prospective program Jiangsu Province (BY2016022-12).

References

Zhang

J.Z.

, Multi -path routing protocol of node cover layer in WSN, Computer Engineering and Applications Computer Engineering and Application46(8) (2010), 87–91.

Chen

, Han

, Wei

, et al., Application research on uneven clustering algorithm in low redundancy WSN, Computer Engineering40(8) (2014), 12–14.

Huang

, Jin

X.Y.

, Zhang

, et al., Energy consumption balanced WSN routing protocol based on GASA’, Chinese Journal of Sensors and Actuators22(4) (2009), 586–592.

Heinzelman

W.B.

, Chandrakasan

A.P.

and Balakrishnan

, An application-specific protocol architecture for wireless microsensor network, IEEE Transactions on Wireless Communications4(1) (2002), 660–670.

C.F.

, Chen

G.H.

, Wu

, et al., An uneven cluster-based routing protocol for wireless sensor networks, Chinese Journal of Computers30(1) (2007), 27–36.

Wang

, Research on an Improved EEUC routing Protocol for WSN, Nanjing: Nanjing University of Posts and Telecommunications, 2013.

Campobello

, Leonardi

and Palazzo

, Improving energy saving and reliability in wireless sensor networks using a simple CRT-based packet-forwarding solution, IEEE/ACM Transaction on Networking20(1) (2012), 191–205.

Liu

, Research of LEACH Protocol Based On the cluster heads election and multi-hop routing, Chong QingčžXi Nan University, 2013.

Zhang

W.W.

, Wang

, Qin

L.L.

, et al., An improvement of LEACH protocol based on energy and distance, Computer Simulation29(3) (2010), 136–160.

10.

Deng

Y.P.

, Tang

, et al., Multi-hop clustering routing protocol with low energy consumption based on control, Journal of Computer Applications33(1) (2013), 108–111.

11.

Hong

J.-H.

, Wuand

C.-H.

and Wu

C.-W.

, RSA cryptosystem design based on the Chinese remainder theorem: Proceedings of ASPDAC, Yokohama, Japan, 2001, pp. 391–395.

12.

Arutselvan

and Maheswari

Mrs.R.

and M.S., Improving Reliability and Energy Efficiency Using Packet Splitting Based On CRT Forwarding Technique and Kalman Filter in Wireless Sensor Networks: Proceedings of 2013 International Conference on Information Communication and Embedded Systems, South Korea, 2013, pp. 701–705.

13.

Campobello

, Leonardi

and Palazzo

, A Novel Reliable and Energy-Saving Forwarding Technique for Wireless Sensor Networks: Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, New York, 2009, pp. 269–278.