See

discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/303872301

An Efficient Tree-based Self-Organizing

protocol for Internet of Things

Article in IEEE Access June 2016

DOI: 10.1109/ACCESS.2016.2578298

CITATIONS READS

16 51

5 authors, including:

Tie Qiu Yu Zhou

Dalian University of Technology Dalian University of Technology
99 PUBLICATIONS 363 CITATIONS 14 PUBLICATIONS 75 CITATIONS

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Research of Queuing Mechanism and Assuring QoS for Emergency Response in Internet of Things
View project

Research on Robustness for Large-Scale Heterogeneous Sensor Networks in Interent of Things View
project

All content following this page was uploaded by Tie Qiu on 26 July 2016.

The user has requested enhancement of the downloaded file.

SPECIAL SECTION ON GREEN COMMUNICATIONS AND NETWORKING FOR 5G WIRELESS

Received May 1, 2016, accepted May 14, 2016, date of publication June 8, 2016, date of current version July 22, 2016.
Digital Object Identifier 10.1109/ACCESS.2016.2578298

An Efficient Tree-Based Self-Organizing Protocol

for Internet of Things
TIE QIU1 , (Senior Member, IEEE), XIZE LIU1 , LIN FENG2 , YU ZHOU2 ,
AND KAIYU ZHENG1 , (Student Member, IEEE)
1 School of Software, Dalian University of Technology, Dalian 116620, China
2 School of Innovation and Entrepreneurship, Dalian University of Technology, Dalian 116024, China
Corresponding author: L. Feng (fenglin@dlut.edu.cn)
This work was supported in part by the Fundamental Research Funds for the Central Universities under Grant DUT16QY27 and in part by
the National Natural Science Foundation of China under Grant 61202443.

ABSTRACT Tree networks are widely applied in sensor networks of Internet of Things (IoTs). This paper
proposes an efficient tree-based self-organizing protocol (ETSP) for sensor networks of IoTs. In ETSP, all
nodes are divided into two kinds: network nodes and non-network nodes. Network nodes can broadcast
packets to their neighboring nodes. Non-network nodes collect the broadcasted packets and determine
whether to join the network. During the self-organizing process, we use different metrics, such as number
of child nodes, hop, communication distance, and residual energy to reach available sink nodes weight;
the node with max weight will be selected as a sink node. Non-network nodes can be turned into network
nodes when they join the network successfully. Then, a tree-based network can be obtained one layer by one
layer. The topology is adjusted dynamically to balance energy consumption and prolong network lifetime.
We conduct experiments with NS2 to evaluate ETSP. Simulation results show that our proposed protocol
can construct a reliable tree-based network quickly. With the network scale increasing, the self-organization
time, average hop, and packet loss ratio will not increase more. Furthermore, the success rate of packet in
ETSP is much higher compared with ad hoc on demand distance vector routing and destination sequenced
distance vector routing.

INDEX TERMS Internet of Things, self-organization, tree-based sensor networks, lifetime.

I. INTRODUCTION Therefore, how to build a tree-based network with a maxi-

Internet of Things (IoTs) [1], [2] enables objects to col- mum lifetime for sensor networks of IoTs has become a crit-
lect or exchange data using many network technologies, ical issue at present. But choosing a real maximum lifetime
such as sensor networks, wireless communication, data tree from all extended trees is a NP-complete problem [15].
collection [3][5], etc. Among them, sensor network is So in order to meet the requirement of real-time, we need to
indispensable to IoTs. It has been widely used in localiza- choose a sub-optimal network. In [16], Zhu et al. have proved
tion [6], industrial automation, environmental monitoring [7] that a tree-based network cannot be built within a polynomial
and other applications. Sensor networks consist of a lot of time. They construct a spanning tree in polynomial time
low-cost, low-power tiny sensor nodes which are randomly through subset division. Even in the worst case the tree can be
distributed. These nodes can communicate with each other to constructed within an exponential time. WSTDO (Weighted
collect and forward sensing data. With the scale increasing Spanning Tree Distributed Optimization) [17] is a distributed
and devices updating, the network system becomes more and data transmission technology based on spanning tree and
more complex. The memory, energy and ability of computing the network performance depends on density of nodes.
are limited by network nodes [8], [9]. In order to maximize It achieves a better performance in sparse networks.
lifetime, many researchers [10] apply themselves to control Ye et al. in [18] have verified that without data aggregation the
network topology [11], build better data transmission route upper limit of all one-hop nodes energy consumption is 98%.
and balance energy consumption of nodes [12][14]. LBT (Load-Balanced and energy-efficient Tree) can maxi-
Tree network is essentially a combination of bus network mize the network lifetime. Authors take load-balancing and
and star network, which can prolong the lifetime of network. energy-efficient of one-hop nodes into account to construct

2169-3536
2016 IEEE. Translations and content mining are permitted for academic research only.
VOLUME 4, 2016 Personal use is also permitted, but republication/redistribution requires IEEE permission. 3535
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
 T. Qiu et al.: ETSP for IoTs

the tree-based network. Algorithm LBT can preserve that the a cluster-header candidate set based on the residual energy
energy consumption of the tree-based network is close to of nodes and then selects a best cluster-header from the can-
the upper limit, approximately. Data aggregation technology didate set based on distance. The simulation results show that
isnt used in above literatures. So these methods increase the EEDC outperforms than LEACH and HEED. Different form
energy consumption and network load when data aggregation HEED, new cluster head is reelected when old cluster head
occurs. In this paper we use the data aggregation technology needs to balance energy consumption in ECBDA (Energy
in tree-based network to reduce the energy consumption and efficient Cluster Based Data Aggregation) [26]. The selection
network load. of cluster-header isnt periodic. In [27], Jin et al propose a new
In this paper, an Efficient Self-organization Proto- algorithm to build data transmission routes with multi-path
col (ETSP) in tree-based network is proposed. The network disjoint protocol. The new algorithm improves the energy-
nodes (the nodes that have joined the network) are classified efficiency of nodes and ensures that the network has a higher
into three types: root node, sink node, sensor node. In the QoS (Quality of Service). But each node contains multi-path
beginning of ETSP, there is only a root node whose hop is that increases the complexity of the network management.
zero. Then, the root node searches child nodes by broad- We extend Energy-efficient Self-organization Routing
casting packets. After receiving the broadcast packets, the Strategy (ESRS) [28] for tree-based wireless sensor networks
neighboring non-network nodes record the topology infor- which is proposed in our previous work and address the above
mation and use different metrics such as number of child problems to construct a reliable tree-based network quickly.
nodes, hop, communication distance and residual energy to
reach available sink nodes weight. Next, the node with max B. PROBLEM STATEMENT
weight is selected as sink node. When non-network nodes At present, there are three kinds of route algorithm of Ad hoc
join the network successfully, they can be turned into network network:
nodes at once. Our proposed algorithm can build a tree- (i) Table driven routing algorithm [29]: DSDV (Des-
based network quickly. In addition, we adjust the topology tination Sequenced Distance Vector Routing) [30],
dynamically and remove the farthest child node to balance WRP (Wireless Routing Protocol);
energy consumption and prolong the whole network lifetime. (ii) Demand driven routing algorithm: AODV (Ad hoc
The rest of this paper is organized as follows: On Demand Distance Vector Routing) [31],
In Section II, we discuss the related work and research DSR (Dynamic Source Routing), ABR (Associativity
problem. The energy-efficient self-organization strategy for Based Routing), SSA (Signal Stability Based Adaptive
tree-based networks is presented in Section III. Section IV Routing), LBR (Link Life Based Routing);
gives the implementation of ETSP. The experiments and (iii) Layer type of area routing algorithm: CGSR (Cluster-
experimental results are discussed in Section V. Section VI head Gateway Switch Routing) [32], ZRP (Zone Rout-
is the conclusion of this paper. ing Protocol).
For AODV and DSDV, the success rate of packet declines
II. RELATED WORK AND PROBLEM STATEMENT significantly with the number of nodes increasing, therefore
A. RELATED WORK they are not suitable for large-scale sensor networks and the
The strategies based on topology control can be divided network performance will decrease rapidly with the increase
into the three types: Multi-node transmit [19], Connected of node number. Hence, we need a more reliable network
dominating set [20], Clustering algorithm [21]. Among model and route algorithm to improve the reliability of com-
them, clustering algorithm is widely used. LEACH (Low munication in large-scale network.
Energy Adaptive Clustering Hierarchy) [22] is one of clus- Eq. 1 is an energy model [33]. Assuming that the dis-
tering algorithms, which creates and maintains clusters to tance between nodei and nodej is d and the packet length
lower the energy of network. Each node uses a stochastic is L bits, the energy cost of sending L bits data is Ei,j (L, d)
algorithm to determine whether it becomes a cluster head. and Er,x (L, d) is the energy cost of receiving L bits data. Ec is
The node with the maximum energy is selected as the the basic energy consumption of send-receive link. dcr is the
cluster head. HEED (Hybrid Energy-Efficient Distributed threshold of communication distance. e1 and e2 are energy
Clustering) [23] is also based on clustering topology. Except units, corresponding to d < dcr and d > dcr . The result of
for residual energy, HEED considers the number of neigh- this energy model is determined by d in practical application.
boring nodes and degrees in cluster head selection. The So we can select the closest node as sink node, which is good
network is stabile when there are no hot nodes during a for reducing the energy consumption.
period. However, LEACH and HEED still reelect the cluster-
Ei,j (L, d) = Et,x (L, d) + Er,x (L, d) = L 2Ec + ed s


header after a period, which wastes some energy. In [24], (
Chen et al. propose an improved LEACH. In this algorithm, e1 , S = 2 if d < dcr
it consumes more energy consumption than LEACH when e= (1)
e2 , S = 4 if d > dcr
there is only one hop between cluster and BS (Base Station).
A new algorithm named EEDC (Energy-Efficient Distance- In addition, we also consider the average hop of net-
based Clustering) is proposed in [25]. First EEDC builds work when selecting sink node. Figure 1 is a sensor

3536 VOLUME 4, 2016

T. Qiu et al.: ETSP for IoTs

between two nodes. The more hops there are, the more trans-
mission times will be. With the increasing of transmission
times the total energy consumption will increase. So we need
to control the hop of network. If a sink node has more child
nodes it will receive more packets and consume more energy
during a certain period. So for balancing energy consumption
we need to take number of child nodes into account to select
sink node. According to Eq. 1, the distance between two
nodes is considered and the energy is lower with the distance
decreasing. We consider [34, eqs. 5 and 6] and balancing hop,
residual energy, number of child nodes and distance between
two nodes, and sink nodei s weight is given by Eq. (2).

Wi = + + Ei + (2)
Di Ni + 1 Hi + 1
Here, Wi is nodei s weight. Ei is nodei s residual energy.
Di is the distance between current node and nodei . Ni is the
FIGURE 1. A sensor network topology.
number of nodei s child nodes. We define the hop of root node
is 0 and other nodes hops are their sink nodes hops plus 1.
Hi is the hop of nodei . , , and are normalized param-
network topology. Node6 can communicate with eters of these four factors and they are defined as follows:
Node5 and Node1. Node6 is closer to Node5. If Node6 selects if the maximum transmission distance is 15 m we set = 15.
Node5 as sink node its hop is (HNode1 + 2), else if Node6 If the maximum number of child nodes is 5 we set = 6. The
selects Node1 as sink node its hop is (HNode1 +1). We assume initial energy of node is random and if the maximum initial
that d1 = 6m, d2 = 7m, d = 12m, according to Eq. 1 energy is 20 J we set = 1/20. If the maximum hop is 10
Node6 selects Node5 as sink node is more energy-efficient. we set = 11.
If d1 = 6m, d2 = 7m, d = 8m, Node6 selects Node1 as sink Nodes of network can be divided into three types: root
node is more energy-saving. So we need to take distance and node, sink node and sensor node. Root node is a special node
hop of nodes into account to select sink node. whose energy is unlimited and it is active all the time. Root
The sink node selection also needs to take the number of node is the first network node and at the beginning root node
child nodes into account. In Figure 1 we assume that Node6s sends broadcast packets to search child nodes. Non-network
sink node can be Node1, Node4 or Node5, but Node1 is the node saves the broadcast packets and calculates the weight of
best. Node1 has 4 child nodes and if Node6 selects Node1 that sink nodes based on Eq. 2. Finally, non-network node selects
will increase the energy consumption of Node1 and shorten the best sink node with maximum weight to join the network.
the lifetime of network. If Node6 selects Node5 or Node4 If the best sink node refuses the non-network node to join
as sink node that can reduce the energy consumption and the network, the non-network node needs to select the sub-
mitigate packet processing pressure of Node1. Here, we optimal sink node, third-optimal sink node until it has joined
assume that residual energy of Node5 is more than Node4 the network successfully. If the non-network node cannot join
and Node5 is better than Node4. For prolonging lifetime we the network after scanning all available sink nodes, it needs
choose Node5 as sink node. After a period of time Node6 can to clear all available sink nodes information and then saves
reelect Node4 as sink node to balance energy consumption of other broadcast packets to reelect an available sink node.
Node5 and Node4. Non-network node begins to select child nodes after joining
During the self-organizing process of tree-based network the network. Centering on the root node we can construct
we need to take distance, hop, number of child nodes and a tree-based network quickly through broadcast searching
residual energy into account. But how to balance these factors and the tree-based network balances the hop, residual energy,
and build a better tree-based network are research points of number of child nodes and distance of nodes.
this paper.
B. DYNAMICALLY ADJUST TOPOLOGY
III. EFFICIENT TREE-BASED SELF-ORGANIZING In the following two cases we have to reconstruct the network
PROTOCOL partially.
A. NETWORK SELF-ORGANIZATION Case 1 (Energy Consumption): The sink node not only
During the process of network construction, network nodes gathers the data of its own sensor but also aggregates data
search child nodes through sending broadcast packets. of all its child nodes, so the energy consumption is quicker
Non-network nodes select sink node according to the received than sensor nodes. The farthest node will be deleted when
broadcast packets. The selection of sink node balances the the energy of the sink node drops below R%. R% is based on
hop, residual energy, number of child nodes and distance the residual energy of last topology changing, which means

VOLUME 4, 2016 3537

 T. Qiu et al.: ETSP for IoTs

the sink node adds or removes a child node. Removing a In Figure 1, we assume that Node6 selects Node5 as its
child node equals sending packets to inform the child nodes to sink node. After a period of time, Node1 cannot work as a
reelect sink node and at the same time delete the information sink node. Node5 needs to reelect a sink node and within
of the child nodes from child node table. It is benefit to bal- one hop range there are no other nodes except for child
ance the energy consumption if the farthest child node joins nodes. Node5 broadcasts to inform all child nodes to reelect
in other branches of the network. In order to compute using sink node. All child nodes can get the biggest weight of
Eq. 3 we have to know the number of child nodes N . A simple their available sink nodes based on Eq. 2 and then send the
example: we assume N = 5 at the moment t0 and residual biggest weight to Node5. Node5 selects the biggest value
energy is E0 . After a certain time at t1 the residual energy from the received weights of all child nodes and informs the
is E1 and E1 = 5E0 /6. For balancing energy consumption, node to reelect sink node. Here we assume that Node6 is the
we delete the farthest child node. Here we assume that the selected node and Node6 reelects Node4 as its sink node.
farthest child node joins in other branches of the network and Node5 removes Node6 from its child node table and requests
the number of child nodes N = 4. At moment t2 , the residual joining in the branch of Node6. During the process of network
energy is E2 and E2 = 4E1 /5, we need to adjust the topology reorganization, if the hop of the sink node is changed it needs
again for energy balance. to inform all its child nodes to update their hops.
Case 2 (Link Failure): Child node sends data packets to its
N
R= (3) sink node periodically and sink node also periodically sends
N +1 response packets to its child nodes to ensure the links are
There are 7 nodes as shown in Figure 1. In the begin- connected. If a sink node has not received any data packet
ning Node1 is the sink node of Node2, Node5 and Node6. from a child node in a certain period it judges the link is
After a period of time the residual energy of Node1 reduces unsuccessful and removes the child node from its child node
one fourth and based on Eq. 3 we delete the farthest child table. If a child node has not received any response packet
node. Here we assume Node6 is the farthest child node. from its sink node in a certain period it will judge the link is
Node1 sends a packet to inform Node6 to reelect sink node. unsuccessful and re-select sink node.
Node6 searches sink node through broadcast. After broadcast
searching, Node6 receives the information of Node4, Node5 C. NETWORK PERFORMANCE EVALUATE
and Node1. According to Eq. 2, Node6 calculates the weight The nodes of sensor networks are deployed randomly in a
of following three types of sink nodes. test area. All nodes have to construct a network quickly so
(i) The weight of Node1 is the largest. Node6 keeps the the self-organizing efficiency is a very important factor [35].
state and other nodes do nothing. We need to ensure the network is robust and the real-time per-
(ii) The weight of Node4 or Node5 is the largest. First formance of data transmission is high when sensor networks
Node6 sends a packet to Node1 to leave the network, are collecting data. With the number of hops increasing, the
and then sends packets to Node4 or Node5 to request forwarding time increase. Thus, the average hop of network
joining the network. and energy of nodes are important aspects to evaluate per-
(iii) The weights of Node1 and Node5 are same or formance for a network. The network lifetime is divided into
the weights of Node1 and Node4 are same, we three types [36]:
need to compare the hop, ratio of residual energy, (i) FND (First Node Dies): The time from network starts
number of child nodes and distance. The priority to the first node dies.
selection standards are: less hop, greater ratio of (ii) LND (Last Node Dies): The time from network starts
((residual energy)/(number of child node + 1)), less to the last node dies.
distance. So Node1 is better. Node1 is its current sink (iii) PND (Percent Nodes Die): The time from network
node so we need not do anything. starts to percent nodes die, for example, P% nodes die.
(iv) The weights of Node4 and Node5 are same, we need The initial values of energy are different for each node.
to compare the hop, residual energy with child nodes In this paper, we select PND and define the network is
number and distance. Here, we assume all factors of unavailable when some key nodes of the network died.
Node4 and Node5 are same, next we need to check
their sink nodes. The sink node of Node5 is Node1 and IV. ALGORITHM DESIGN
Node1 is the sink node of Node6. Node6 reelects sink A. NETWORK SELF-ORGANIZATION
node is to balance the energy consumption of Node1. 1) SELECT THE BEST SINK NODE
If Node6 reelects Node5 as its sink node, the length In the beginning of ETSP, many non-network nodes that are
of the packet from Node5 to Node1 will increase. in sleep mode exit in the network. Then, one of the non-
Furthermore, it increases the energy consumption of network nodes builds a network and turns into a network
Node1 according to Eq. 1. However, Node4 isnt in the node. At the same time, the network node sends some broad-
branch of Node1 and if Node6 joins in the branch of cast packets and switches into network monitor state. Next,
Node4 that can help to balance the energy consumption non-network nodes which receive the broadcast packet start a
of Node1. timer and save the node ID of network node which sends the

3538 VOLUME 4, 2016

T. Qiu et al.: ETSP for IoTs

Algorithm 1 Select the Best Sink Node is full. If the array child[] is full, the network node sends
1: i 0, max_weight 0, sink_index 0 a PT _DENIED (Packet from sink node to deny the non-
2: while i < ava_sink_num do network node joins the network) packet to the non-network
3: calculate the weight W node where the PT _JOIN _REQUEST packet is from. Other-
4: optional_sink[i].weight W wise, the network node will send a PT _ACCEPTED (Packet
5: i++ from sink node to accept the non-network node joins the
6: if max_weight < W then network) packet. Finally, the non-network nodes that receive
7: sink_index i the reply of network decide whether or not to join the network
8: max_weight W based on the type of reply packet. When the received packet
9: else if max_weight = W then is PT _ACCEPTED, it becomes a network node (Line 4).
10: if optional_sink[i] is greater then If a node receives a PT _DENIED packet (Line 5), it needs to
11: sink_index i reselect a sub-optimal sink node (Lines 7-20). If max_weight
12: max_weight W is equal to 0 (Line 21), it means that there is no available sink
13: end if node and the non-network node cant join the network. Then
14: end if it sets ava_sink_num to 0 and waits for other nodes searching
15: end while (Lines 22-23). Otherwise, it updates sink_index and goes to
16: Output:sink_index Line 1 to rejoin network (Line 26).
There is one loop to scan array optional_sink[] and the
array length is ava_sink_num. ava_sink_num is numerable
and the complexity of Algorithm 2 is O(n).
broadcast packet in array optional_sink[]. The best sink node
in array optional_sink[] is selected based on Eq. 2 until the B. REORGANIZATION OF HOT AREA
timer expires. The detail algorithm is shown in Algorithm 3. 1) CHECKING RESIDUAL ENERGY OF SINK NODE
Variable max_weight is used to record the maximum weight For prolonging the network lifetime and balancing energy
of all available sink nodes. Variable sink_index represents consumption, ETSP needs to check the sink nodes resid-
the index of sink node in array optional_sink[]. They are ual energy. When a sink node adds or deletes a child
initialize to 0 in Line 1. Variable ava_sink_num records the node it updates Eorg (The residual energy of last topology
number of available sink nodes. The node calculates the change) with Eava . The farthest node will be deleted
weight of all available sink nodes base on Eq. 2 and records when the energy of the sink node drops below R%.
the results in optional_sink[].weight (Lines 3-4). The node The related algorithm is shown in Algorithm 3. Variable
gets the index of the best sink node by comparing weights energy_check_timer records the timer value of energy check.
(Lines 6-8). If more than one nodes have the max weight at Variable ENERGY _CHECK _TIMER records the initialize
the same time, it elects the better one by the standard of less value of energy check timer. If energy_check_timer expires
hops, greater ratio of R and less distance (Lines 9-12). Finally, and the current energy drops below R% (Line 1), the sink
it outputs the results (Line 16). node sends a PT _DELETE packet to the farthest child node
There is one loop in Algorithm 1 to scan array (Line 2) and updates Eorg (Line 3). Otherwise it exists
optional_sink[] and the array length is ava_sink_num. current procedure (Lines 4-6). If a sink node receives a
ava_sink_num is determined by the limited density of net- PT _DELETE_OK packet from the child node (Line 7),
works, therefore the ava_sink_num is numerable and the it removes the record of farthest child node (Line 8) and
complexity of Algorithm 1 is O(n). All nodes can select a updates the number of child nodes (Line 9). If N is equal
best sink node rapidly. to 0 (Line 11), it becomes a non-network node (Line 12).
Otherwise, it resets the energy_check_timer for next round
2) NON-NETWORK NODES JOIN IN NETWORK (Line 14).
After selecting the best sink node, non-network nodes There is no loop in Algorithm 3, thus the
request to join the network. The related process is shown is O(1). However, after sending a PT _DELETE (Packet from
in Algorithm 2. Variable sink_index_tmp records the index sink node to delete a child node) packet the node starts a timer
of sink node in array optional_sink[]. Variable Eava is the to wait the reply and it will cost some time. If a node receives
residual energy of node. The boolean variable is_net_node a PT _DELETE packet or doesnt receive any reply packet
identifies whether the node is a network node. According during a period, it needs to reelect sink node.
to the results of Algorithm 1, the non-network node sends a
PT _JOIN _REQUEST (Packet of non-network node requests 2) PROCESS OF REORGANIZATION
to join the network) packet to the best sink node (Line 1). The node deleted by its sink node due to low energy
Then the node starts a timer and saves the received packets needs to rejoin the network. The related process is shown
during the timer (Line 2). When the network node receives in Algorithm 4 and Algorithm 5. After initialization (Line 1),
the PT _JOIN _REQUEST packet, it checks whether the array the node broadcasts PT _SINK _SEARCH messages and starts
child[] (An array to record the ID of current child nodes) a timer (Line 2). Before the timer expires, if the node receives

VOLUME 4, 2016 3539

 T. Qiu et al.: ETSP for IoTs

Algorithm 2 Non-Network Node Requests to Join in Algorithm 3 Check Energy Consumption of Sink Node
Network 1: if energy_check_timer = 0 && (Eava /Eorg ) (R =
1: Send PT _JION _REQUEST to node N /(N + 1)) then
optional_sink[sink_index] 2: send a PT _DELETE packet to the farthest child node
2: Start a timer. The node receives and saves packets during 3: Eorg Eava
the timer 4: else
3: if the node receives a PT _ACCEPTED packet then 5: return
4: is_net_node true 6: end if
5: else if the node received a PT _DENIED packet then 7: if sink node receives PT _DELETE_OK then
6: i 0, max_weight 0, sink_index_tmp 0; 8: remove the farthest child nodes record
7: while i < ava_sink_num do 9: N N 1
8: if optional_sink[i].weight 10: end if
optional_sink[sink_index].weight && i 6 = sink_index 11: if N = 0 then
then 12: is_net_node false
9: if optional_sink[i].weight > max_weight 13: else
then 14: energy_check_timer
10: sink_index_tmp i ENERGY _CHECK _TIMER
11: max_weight optional_sink[i].weight 15: end if
12: else if optional_sink[i].weight =
max_weight then
13: if optional_sink[i] is greater then Algorithm 4 Reorganizing the Hot Area
14: sink_index_tmp i 1: ava_sink_num 0, sink_index 1, i 0,
15: max_weight is_sink_node false
optional_sink[i].weight 2: Broadcast PT _SINK _SEARCH and start a timer
16: end if 3:
17: end if 4: Before timer expires
18: end if 5: if the node receives ACK then
19: i++ 6: update optional_sink[]
20: end while 7: ava_sink_num++
21: if max_weight = 0 then 8: end if
22: ava_sink_num 0 9:
23: return 10: if ava_sink_num = 0 then
24: else 11: if is_net_node = false then
25: sink_index sink_index_tmp 12: go to Line 1
26: go to Line 1 13: else
27: end if 14: execute algorithm 5
28: end if 15: end if
16: else
17: execute Algorithm 1 and 2
18: if nodes hop is changed then
a reply packet ACK from sink node (Line 5), it saves node ID
19: inform child nodes to update hop
in array optional_sink[] (Line 6) and updates ava_sink_num
20: end if
(Line 7). After the broadcast searching, if ava_sink_num is
21: end if
equal to 0 (Line 10), it means that there is no available sink
node within one hop range. If the node is a non-network node,
it goes to Line 1 to keep searching (Line 12). Otherwise, it can
select the best sink node from its child nodes by executing But there is a certain time interval between two packets
Algorithm 5 (Line 14). If ava_sink_num is more than 0 sending and it consumes some time.
(Line 16), it carries out the procedures in Algorithms 1 and 2 In Algorithm 4, if there is no available sink node within
to join the network (Line 17). If the nodes hop is changed one hop range except for child nodes, the node ought to
after being a network node, it needs to inform its child inform all its child nodes to reorganize. After that it selects
nodes to update their hops before existing current procedure a best sink node from its child nodes. The detail information
(Lines 18-19). is shown in Algorithm 5. Variable max_child_weight is the
There is one loop in the Algorithm 4. The total costs are the max weight of all child nodes. The weight of child node is
times of sending PT _SINK _SEARCH (Broadcast packet of the maximum weight of its available sink nodes. Variable
non-network node to search available sink node) packets and max_child_weight_index is the index of max_child_weight
it is limited. So the complexity of Algorithm 4 is O(n). in array child[]. At first, the sink node needs to clear array

3540 VOLUME 4, 2016

T. Qiu et al.: ETSP for IoTs

Algorithm 5 Network for the Child Nodes child[] (Line 1), then it sends a PT _REELECT _SINK packet
1: clear array child[] to all the child nodes for reelecting sink node (Line 2).
2: send PT _REELECT _SINK to the child nodes At the same time, it starts a timer (Line 3). If a node receives
3: start a timer a PT _REELECT _SINK packet from its sink node (Line 4),
4: if a node receives PT _REELECT _SINK then it sets ava_sink_num to 0 and clears optional_sink[] (Line 5).
5: ava_sink_num 0 and clears optional_sink[]; Then it broadcasts PT _SINK _SEARCH messages (Line 6).
6: broadcast PT _SINK _SEARCH After that, the child node needs to calculate the weights of all
7: calculate the weights of sink nodes; available sink nodes according to Eq. 2 (Line 7) and sends
8: send the biggest weight is to the sink node the biggest weight to its sink node (Line 8). The sink node
9: end if needs to record the received information in array child[] and
10: the sink node selects the maximum weight from child[] select the maximum weight when the timer expires (Line 10).
11: send PT _REJOIN _REQUEST to Then it sends a PT _REJOIN _REQUEST packet to node
child[max_child_weight_index] child[max_child_weight_index] (Line 11). When the child
12: if a child node receives PT _REJOIN _REQUEST then node receives a PT _REJOIN _REQUEST packet (Line 12), it
13: is_net_node false needs to become a non-network node and join the network by
14: execute algorithm 2 executing Algorithm 2 (Lines 13-14). If the node succeeds in
15: if is_net_node = true then rejoining the network (Line 15), it adds the original sink node
16: add the old sink node to its child node table to its child node table and sends a PT _REJOIN _OK packet
17: send PT _REJOIN _OK to the old sink node to the original sink node (Lines 16-17). Otherwise it becomes
18: else a network node and replays a PT _REJOIN _FAILED
19: is_net_node true packet to the original sink node (Lines 19-20). If the
20: sent PT _REJOIN _FAILED to the old sink node sink node receives a PT _REJOIN _OK packet, go to
21: end if Line 16 (Line 14), it supposes to delete child node
22: end if child[max_child_weight_index] from the child node table
23: if sink node receives PT _REJOIN _OK then and sets child[max_child_weight_index] as its sink node
24: delete child[max_child_weight_index] (Lines 23-24). It becomes a network node and sends packets
25: is_net_node true to inform its child nodes to update their hops (Line 25).
26: return If the sink node receives a PT _REJOIN _FAILED packet
27: else if sink node receives PT _REJOIN _FAILED then it needs to select a sub-optimal child node (Lines 30-41).
28: i 0, max_child_weight 0 If max_child_weight is equal to 0 (Line 44), it means there
29: while i N do is no available child nodes and the reconstruction fails,
30: if child[i].weight it exists current procedure to reelect available child nodes
child[max_child_weight_index].weight && i 6= (Line 45). Otherwise it sends a PT _REJOIN _REQUEST
max_child_weight_index then packet to child[max_child_weight_index] and goes to
31: if child[i].weight > max_child_weight then Line 12 (Lines 47-49). There are two loops in Algorithm 5,
32: max_child_weight_index i it scans the array optional_sink[] and the array length is
33: max_child_weight child[i].weight ava_sink_num at first, so the complexity is O(n). The times of
34: else if child[i].weight = max_child_weight second loop is the number of child nodes. The number of child
then nodes is less than the length of array child[]. In conclusion,
35: max_child_weight_index i the maximum algorithm complexity in ETSP is O(n), which
36: max_child_weight child[i].weight is similar to AODV and DSDV.
37: end if
38: i++
V. SIMULATION AND ANALYSIS
39: end if In order to validate our proposed model, we utilized NS2
40: end while to simulate. The new ETSP protocol has three functions:
41: end if
self-organize tree-based network, balance energy consump-
42: if max_child_weight = 0 then
tion, reelect sink node. TABLE 1 lists the simulation
43: return parameters.
44: else
Before building a tree-based network we need to set param-
45: sent PT _REJOIN _REQUEST to eters based on TABLE 1. According to TABLE 1, the maxi-
child[max_child_weight_index] mum communication radius is 15 m so is 15. The maximum
46: go to Line 12; number of child nodes is 10 so is 11. The maximum init-
47: end if
energy is 29 J so is 1/29. The maximum hop is 10 so is 11.

VOLUME 4, 2016 3541

 T. Qiu et al.: ETSP for IoTs

FIGURE 2. Topology of self-organization. (a) Root coordinates: (0,0). (b) Root coordinates: (50,50).

TABLE 1. Simulation parameters. TABLE 2. Experiment settings.

selection of sink node is based on the least hop which between

the node and available sink node. Distance indicates that the
selection of sink node is based on the least distance between
the node and available sink node. Left Energy indicates that
the selection of sink node is based on the maximum residual
energy of available sink node. Child Number indicates that
the selection of sink node is based on the number of each child
nodes available sink node. ETSP indicates that the selection
of sink node is based on Eq. 2 and takes the four factors into
The topology of ETSP is given in Fig. 2 accord- account.
ing to the information of self-organization process. It can be observed that they are all linearly increasing
In the simulation, 100 sensor nodes are randomly deployed in with node number increasing in Fig. 3. But the slope of self-
the area of 100m*100m. In Fig. 2a, the root rode whose coor- organization time in ETSP is smaller. Therefore ETSP can
dinates are (0,0) is in the border of network. While in Fig. 2b, construct a reliable tree-based network quickly in the large
the root node is located at the center of the simulation area. scale network. This process will be faster if the root node
It can be seen that the results of self-organization are different in the center of network. In Fig. 4, the increasing trends of
due to the differ of root nodes location, but every node average hop are similar except for the networks based on
succeeds in joining the network. For the topology in Fig. 2b, Distance and Left Energy. They are lager when the node
the average hop is 4.35, less than 8.02 hops in Fig. 2a. number is over 500. Thus, they need more transmission times
Furthermore, the re-organization time is 3.03 s, faster than and energy consumption increases. If the root node is located
4.62 s in Fig. 2a. The average energy consumption is 0.34J , at the center of network, it needs less average hop to construct
less than 0.36J in Fig. 2a. Thus, ETSP can achieves a better a network, which speeds up the self-organization process.
performance if the root node is in the center of network. Network lifetime which illustrated in Fig. 5 is limited by
In order to verify the efficiency of ETSP, five groups energy consumption. The network based on Hop has the
experiments based on the different scales are conducted. The longest lifetime due to sending less packets. While ETSPs
experiment settings are shown in TABLE 2. In each group, lifetime is a little shorter than others. We can conclude from
we do five experiments whose results are shown in Fig. 3, Fig. 5a and Fig. 5b that the network lifetime is longer when
Fig. 4, Fig. 5, Fig. 6, and Fig. 7. Hop indicates that the the root node in the center.

3542 VOLUME 4, 2016

T. Qiu et al.: ETSP for IoTs

FIGURE 3. Relationship between Self-organization Time and Number of Nodes. (a) Root Node in the border. (b) Root Node in
the center.

FIGURE 4. Relationship between Average Hop and Number of Nodes. (a) Root Node in the border. (b) Root Node in the center.

FIGURE 5. Relationship between Network Lifetime and Number of Nodes. (a) Root Node in the border. (b) Root Node in
the center.

FIGURE 6. Relationship between Number of Send Packet and Number of Nodes. (a) Root Node in the border. (b) Root Node in
the center.

It can be seen in Fig. 6, for the network based on Hop, the While ETSP is similar to the network based on Distance, Left
number of send packets is less than others. Thus, it decreases Energy and Child Number. Obviously, the location of root
node energy consumption and prolongs the network time. node doesnt affect the number of packets. After constructing

VOLUME 4, 2016 3543

 T. Qiu et al.: ETSP for IoTs

FIGURE 7. Relationship between Success Rate of Packet and Number of Nodes. (a) Root Node in the border. (b) Root Node in the
center.

FIGURE 8. Performance Comparison of Three Route Algorithms. (a) Network lifetime. (b) Success rate of packet.

a network the nodes begin to send and receive data, packet is reasonable. Although the network lifetime is shorter, the
loss is inevitable in this process. The performance of success self-organization time, network average hop, packet number
rate of packet is one of the most critical indicators for a and success rate of packet are balanced.
routing protocol. It can be observed that the network based In Fig. 8, we evaluate the performance of ETSP, AODV
on Child Number and Hop are lower than ETSP in Fig. 7. and DSDV with different number of sensor nodes. The root
With the network scale increasing, the success rate of packet node is located in the center of topology. It can be seen that
in ETSP doesnt decline significantly and its over 92%. the network lifetime of ETSP is longer than DSDV, because it
From the simulation results we know that: the network periodically checks the residual energy of sink node and reor-
based on Hop can get longer lifetime. However its throughput ganize the hot area to achieve energy consumption. Whats
and success rate of packet is lower. The network based on more, the success rate of packet in ETSP is further higher than
Distance can get larger throughput and higher success rate of AODV and DSDV, it keeps stable with the number of sensor
packet, but its self-organization time is longer and average nodes increasing. Thus, the network constructed by ETSP is
hop is bigger. The network based on Left Energy is worse reliable.
and its self-organization time is longer and average hop is
bigger than the network based on Distance. The network VI. CONCLUSION
based on Child Number sends less packets and its success In this paper, we propose an efficient self-organization pro-
rate of packet is lower. The network based on ETSP balance tocol named ETSP for sensor networks of IoTs. ETSP saves
distance, hop, number of child nodes and residual energy. The more energy and has a longer network lifetime by construct-
results in Figure 4 reveal that ETSP can construct a tree-based ing a tree-based network quickly. We use the weight of nodes,
network quickly. With the network scale increasing, the self- including residual energy, hop, number of child nodes and
organization time, average hop and packet loss ratio wont distance between the nodes, to determine whether the node
increase repaidly. During the process of simulation experi- can be a sink node. Thus the depth of tree is optimized by
ment, the sink nodes are about 50% of all nodes and key nodes using ETSP. During the process of data transmission, the
are less than 50%. So we set P = 50 is feasible. Compared network topology changes dynamically. Each sink node will
with each other between Fig. 3a and Fig. 3b, Fig. 4a and be dynamically reselected due to the energy consumption of
Fig. 4b respectively, we can see that the network is worse sink nodes is faster than other nodes. The simulation results
when the root node in the border. The network based on Eq. 2 show that ETSP is able to build reliable tree-based networks,

3544 VOLUME 4, 2016

T. Qiu et al.: ETSP for IoTs

reduces the energy consumption and prolongs the lifetime of [23] O. Younis and S. Fahmy, Distributed clustering in ad-hoc sensor net-
sensor networks. works: A hybrid, energy-efficient approach, in Proc. 23rd Annu. Joint
Conf. IEEE Comput. Commun. Soc., Mar. 2004, pp. 629640.
[24] Y. L. Chen, N. C. Wang, Y. N. Shih, and J. S. Lin, A novel energy-efficient
REFERENCES and distance-based clustering approach for wireless sensor networks,
Wireless Pers. Commun., vol. 75, no. 1, pp. 349368, 2014.
[1] D. Zhang, S. Zhao, L. T. Yang, M. Chen, Y. Wang, and H. Liu, NextMe:
[25] O. Younis and S. Fahmy, Distributed clustering in ad-hoc sensor net-
Localization using cellular traces in Internet of Things, IEEE Trans. Ind.
works: A hybrid, energy-efficient approach, in Proc. IEEE INFOCOM,
Informat., vol. 11, no. 2, pp. 302312, Apr. 2015.
2004, pp. 629640.
[2] H. Ning, H. Liu, and L. T. Yang, Aggregated-proof based hierarchical
[26] S. S. Ranjani, S. R. Krishnan, C. Thangaraj, and K. V. Devi, Achieving
authentication scheme for the Internet of Things, IEEE Trans. Parallel
energy conservation by cluster based data aggregation in wireless sensor
Distrib. Syst., vol. 26, no. 3, pp. 657667, Mar. 2015.
networks, Wireless Pers. Commun., vol. 73, no. 3, pp. 731751, 2013.
[3] L. Atzori, A. Iera, and G. Morabito, The Internet of Things: A survey,
[27] R.-C. Jin, T. Gao, J.-Y. Song, J.-Y. Zou, and L.-D. Wang, Passive cluster-
Comput. Netw., vol. 54, no. 15, pp. 27872805, Oct. 2010.
based multipath routing protocol for wireless sensor networks, Wireless
[4] M. Turkanovi, B. Brumen, and M. Hlbl, A novel user authentication and Netw., vol. 19, no. 8, pp. 18511866, 2013.
key agreement scheme for heterogeneous ad hoc wireless sensor networks, [28] L. Feng, Y. Zhou, and T. Qiu, An energy-efficient self-organization rout-
based on the Internet of Things notion, Ad Hoc Netw., vol. 20, pp. 96112, ing strategy in tree networks, in Proc. 8th Int. Conf. Mobile Multimedia
Sep. 2014. Commun., 2015, pp. 233236.
[5] C. W. Tsai, C. F. Lai, and A. V. Vasilakos, Future Internet of Things: [29] B. S. Manoj and C. S. R. Murthy, On the use of out-of-band signal-
Open issues and challenges, Wireless Netw., vol. 20, no. 8, pp. 22012217, ing in ad hoc wireless networks, Comput. Commun., vol. 26, no. 12,
2014. pp. 14051414, 2003.
[6] G. Han, J. Jiang, C. Zhang, T. Duong, M. Guizani, and G. Karagiannidis, [30] E. C. Perkins and P. Bhagwat, Highly dynamic destination-sequenced
A survey on mobile anchor node assisted localization in wireless sensor distance-vector routing (DSDV) for mobile computers, ACM SIGCOMM
networks, IEEE Commun. Surveys Tuts., to be published. Comput. Commun. Rev., vol. 24, no. 4, pp. 234244, 1994.
[7] S. Lu, Z. Wang, Z. Wang, and S. Zhou, Throughput of underwater wire- [31] C. Perkins, E. Belding-Royer, and S. Das, Ad hoc On-Demand Distance
less ad hoc networks with random access: A physical layer perspective, Vector (AODV) Routing, document RFC 3561, 2003.
IEEE Trans. Wireless Commun., vol. 14, no. 11, pp. 62576268, Nov. 2015. [32] C. C. Chiang, H. K. Wu, W. T. Liu, and M. Gerla, Routing in clustered
[8] J. A. Khan, H. K. Qureshi, and A. Iqbal, Energy management in wireless multihop, mobile wireless networks with fading channel, in Proc. IEEE
sensor networks: A survey, Comput. Elect. Eng., vol. 41, pp. 159176, SICON, Apr. 2014, pp. 177186.
Jan. 2015. [33] K. Khamforoosh, Clustered balanced minimum spanning tree for routing
[9] R. Silva, J. S. Silva, and F. Boavida, Mobility in wireless sensor and energy reduction in wireless sensor networks, in Proc. IEEE Symp.
networksSurvey and proposal, Comput. Commun., vol. 52, pp. 120, Wireless Technol. Appl., Sep. 2011, pp. 5659.
Oct. 2014. [34] H. Zhang, P. Chen, and S. Gong, Weighted spanning tree clustering
[10] G. Han, J. Jiang, N. Bao, L. Wan, and M. Guizani, Routing protocols routing algorithm based on LEACH, in Proc. 2nd Int. Conf. Future
for underwater wireless sensor networks, IEEE Commun. Mag., vol. 53, Comput. Commun., 2010, pp. 22232227.
no. 11, pp. 7278, Nov. 2015. [35] C. Santhi and D. A. Sharmila, A self-organized location aware energy
[11] T. Qiu, L. Chi, W. Guo, and Y. Zhang, STETS: A novel energy-efficient efficient protocol for wireless sensor networks, Comput. Elect. Eng.,
time synchronization scheme based on embedded networking devices, vol. 41, pp. 265274, Jan. 2015.
Microprocess. Microsyst., vol. 39, no. 8, pp. 12851295, 2015. [36] A. Avokh and G. Mirjalily, Dynamic balanced spanning tree (DBST)
[12] S. Lu, V. H. Nascimento, J. Sun, and Z. Wang, Sparsity-aware adaptive for data aggregation in wireless sensor networks, in Proc. 5th Int. Symp.
link combination approach over distributed networks, Electron. Lett., Telecommun., 2010, pp. 391396.
vol. 50, no. 18, pp. 12851287, 2014.
[13] G. Han, A. Qian, J. Jiang, N. Sun, and L. Liu, A grid-based joint
routing and charging algorithm for industrial wireless rechargeable sensor
networks, Comput. Netw., vol. 101, pp. 1928, Jun. 2016.
[14] T. Qiu, D. Luo, F. Xia, N. Deonauth, W. Si, and A. Tolb, A greedy model
with small world for improving the robustness of heterogeneous Internet
of Things, Comput. Netw., vol. 101, pp. 127143, Jun. 2016.
[15] Y. Wu, S. Fahmy, and N. B. Shroff, On the construction of a maximum-
lifetime data gathering tree in sensor networks: NP-completeness and
approximation algorithm, in Proc. IEEE INFOCOM, 27th Int. Conf.
Comput. Commun., Apr. 2008, pp. 10131021.
[16] X. Zhu, X. Wu, and G. Chen, An exact algorithm for maximum lifetime TIE QIU (M12SM16) received the B.E. degree
data gathering tree without aggregation in wireless sensor networks, from the Inner Mongolia University of Tech-
Wireless Netw., vol. 21, no. 1, pp. 281295, 2015. nology, China, in 2003, and the Ph.D. and
[17] L. Carr-Motykov and D. Dryml, Distributed energy efficient data gath- M.Sc. degrees from the Dalian University of
ering without aggregation via spanning tree optimization, in Proc. 12th Technology (DUT), in 2005 and 2012, respec-
Int. Conf. Ad-Hoc, Mobile, Wireless Netw., 2013, pp. 8798. tively. He is currently an Associate Profes-
[18] J. Ye et al., Lifetime optimization by load-balanced and energy efficient sor with the School of Software, DUT, China.
tree in wireless sensor networks, Mobile Netw. Appl., vol. 18, no. 4, He was a Visiting Professor of Electrical and
pp. 488499, 2013. Computer Engineering with Iowa State Univer-
[19] O. Liang, A. Sekercioglu, and N. Mani, Gateway multipoint relays-an sity, USA, from 2014 to 2015. He is as an
MPR-based broadcast algorithm for ad hoc networks, in Proc. 10th IEEE
Editorial Board Member of the Journal of Advanced Computer Sci-
Singapore Int. Conf. Commun. Syst., Oct./Nov. 2006, pp. 16.
ence and Technology, a Gest Editor of computers and electrical engi-
[20] M. Rai, S. Verma, and S. Tapaswi, A power aware minimum connected
neering (Elsevier journal) and ad hoc networks (Elsevier journal),
dominating set for wireless sensor networks, J. Netw., vol. 4, no. 6,
pp. 511519, 2009. a Program Chair of iThings2016, a TPC Member of Industrial IoT2015 and
[21] O. Dagdeviren, K. Erciyes, and D. Cokuslu, A merging clustering algo- ICSN16, a Workshop Chair of CISIS13 and ICCMSE15, a Special Session
rithm for mobile ad hoc networks, in Proc. Int. Conf. Comput. Sci. Appl., Chair of WCC 2012 and CSA13, and a TPC Member of AIA13, EEC14,
2006, pp. 681690. EEC15, and EEC16. He has authored or co-authored six books and over
[22] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, 50 scientific papers in international journals and conference proceedings.
An application-specific protocol architecture for wireless microsensor He has contributed to the development of two copyrighted software systems
networks, IEEE Trans. Wireless Commun., vol. 1, no. 4, pp. 660670, and invented eight patents. He is a Senior Member of China Computer
Oct. 2002. Federation.

VOLUME 4, 2016 3545

 T. Qiu et al.: ETSP for IoTs

XIZE LIU is currently pursuing the bachelors YU ZHOU received the bachelors degree in
degree with the School of Software, Dalian Uni- software engineering and the masters degree in
versity of Technology (DUT), Dalian, China. He is computer application technology from the Dalian
an outstanding student of DUT and has joined University of Technology. He was involved in
in several technology innovations. His research research on embedded system and wireless sen-
interests cover embedded system and Internet of sor networks. He has published three books and
Things. three papers. He was with the Software and Ser-
vice Group, Intela s Asia-Pacific Research Cen-
ter, where he was involved in the development
of software guard extension and the research on
application enclave of the Windows and Linux system.

KAIYU ZHENG received the B.E. degree from the

Dalian University of Technology (DUT), China, in
LIN FENG received the B.S. degree in electronic 2014. He is currently pursuing the masters degree
technology, the M.S. degree in power engineering, with the School of Software, DUT, China. He is
and the Ph.D. degree in mechanical design and an Excellent Graduate Student of DUT and has
theory from the Dalian University of Technology, been awarded several scholarships in academic
China, in 1992, 1995, and 2004, respectively. He is excellence and technology innovation. He partic-
currently a Professor and Doctoral Supervisor with ipated in Open Source Hardware and Embedded
the School of Innovation entrepreneurship, Dalian Computing Contest 2012 and won the First Prize.
University of Technology. His research interests His research interests cover embedded system and
include intelligent image processing, robotics, data Internet of Things.
mining, and embedded systems.

3546 VOLUME 4, 2016

View publication stats