An Enhanced Energy Efficiency Tree-Based Hierarchical Routing Based on Additional Connections ()
1. Introduction
Wireless Sensor Networks (WSNs) is composed by lots of sensor nodes deployed for monitored area in a self-organized multi-hop manner. It is widely used in application scenarios which may hazard safety or healthy, such scenarios as battleground, natural disasters, forecast, health care and nuclear plant. In smart city scenarios, WSNs plays an as important role. One of the basic characteristics of smart city is instrumented [1]. Instrumented refers to that sensors were widely deployed in smart cities to monitor real physical world and then digitize the harvested data into available digital information, which could be processed by information and communications technology (ICT). In practical applications, to affect environment as little as possible, to reduce each node’s energy overhead and to simplify sensor nodes’ operation system complexity, WSN sensor nodes are always in small physical size and embedded as little models as possible.
Some classic routing protocols were developed based on Zigbee protocol. A number of protocols are developed for different scenarios according to sensor nodes density and sensor nodes movement behavior, dynamic or static, and even nodes’ energy supply type. Ad-hoc On-demand Distance Vector (AODV) [2] protocol is mainly adapted in dynamic scenarios. In AODV, a route is set up every time before transmitting packets, which makes it suitable for time-varying environments. However, this advantage is on cost of high latency and more network resource. In previous work [2], we proposed an enhanced AODV routing protocol, selecting route based on the residual energy and link capacity, which improves the performance in network life cycle and average packet delay. AODV is suitable in dynamic environments, for many applications in smart cites, monitored environment change little or even static.
Different from AODV, routing information is kept by parent-child relationship in Tree-based Hierarchical Routing (THR) protocol, better suited for static scenarios. As it doesn’t need to perform route discovery process, its latency performance improves a lot. However, as parent nodes are always more used than child nodes, energy overhead is not uniformly distributed in THR, which will furthermore affect the network life time. X. Li [3] and X. Xu [4] introduced neighbor relationships individually. This neighbor relationship could create shortcut routes between source and its destinations, which could reduce networking latency and save intermediate nodes’ energy overhead. This additional neighbor relationship brings more routing choices, while it could not provide choice priority when some intermediate nodes’ residual energy decreased to threshold, it could neither be able to indicate the shortest path to destination. An urbanizing world needs to keep WSNs technologies innovation and development with time. To provide a more flexible routing technology for static wireless sensor applications, we developed an enhanced THR routing protocol to fulfill functions of providing choice priority, indicating shortest path and resetting topology with minimum costs. To realize these functions, Neighbor, Nephew and Brother Connections were introduced, and address assignment method is realized to create initial topology tree.
Our proposal is mainly based on simulation environment and hardware environment. Simulation environment bases on open source network simulator OMNet++ 4.1. Hardware environment bases on Texas Instruments Chipcon SmartRF®04EB embedded boards and IAR Embedded Workbench, both provided by CMC (Canadian Microelectronics Corporation) Microsystems. We realized THR protocol on OMNet++4.1 network simulator and then tested one source-sink point to point connection on two Chipcon SmartRF®04EB embedded boards.
2. Application Scenarios
Smart city will be a prospective application for WSNs. Sensors could send instrumented data to information consumers via heterogeneous networks, for instance femtocell network in houses or office rooms or even via cellular networks if there is not any other choice.
To lower expenses and increase extensibility during realizing a smart city, IBM smart city solution on cloud [7] would be one of practical choices. In cloud smart city, services are accessible over the Internet via different access networks. IBM’s smart-cloud is an instance to integrate data and manage all services in a city. Wireless sensor systems gather environment information, and then send it to servers nearby after digitized. Preliminary processing will be implemented in servers; afterwards information is transmitted to cloud. In this manner, sensor system could be more lightweight, cheaper and easier to scale up or down the system. History information and policies could be stored in cloud easily, while it is much more difficult to store them in sensor system. If all data stored in cloud, all analysis completed in cloud, coordination and cooperation between different systems need not any data transmission inter-system, which may be time-consuming. Information like history data, policies and data from related system would all benefit for making a wiser decision. For example, traffic system gets smarter if decisions were made based on a comprehensive consideration, which could include not only traffic load but also safety information from police system and rainfall/water-depth data from weather system and what’s more historical traffic information of different road sections of different periods.
Some smart city applications run IP stack on wireless sensors. Contiki [11] is an open source operation system which brings IP to sensor networks. Contiki is light enough to run on wireless sensors, as well as having the ability to integrate TCP/IP stack. It just needs 10KB’s RAM and 30KB’s ROM even though building in TCP/IP stacks. For most application scenarios IP stack is not really necessary. In order to be able to run this THR in a simplifier sensor network, this proposal is not based on IP stack and a more simplified addressing method is designed.
Static or stationary wireless sensor network (S-WSNs), is a network composed by wireless sensors where all the nodes locations are fixed or nearly fixed. Demonstrated applications of S-WSNs in industrial environments are humidity monitoring in Canadian Vegetable Industry [5], temperature monitoring in nuclear reactors [6] etc., or in the nearly coming smart houses [7]. In these scenarios, data is acquired by sensor nodes and then transmitted to server clients via wireless signal in a self-organized manner. To reduce power overhead and improve network life cycle time, optimal routing strategies is required for multi-hop transmission. THR is a suitable routing strategy for S-WSNs. Aim of this enhanced THR routing protocol we proposed is to decrease the latency for data collection and to extend network life time promotes application of S-WSNs in industry environments.
3. Enhanced THR Protocol Based on Additional Relationships
This section provides a description on enhanced THR from two parts: connections and routing methods introduced based on these connections, naming and addressing method.
3.1. Connections and Routing Method
Neighbor, Nephew and Brother Connections together with original Parent/Child relationship, are shown in Figure 1. Neighbors are nodes inside radiation coverage of one node. Brother Nodes are Neighbor Nodes which share a same parent node. Nephews are nodes which are Neighbor Nodes which take Brother node as parent node, lying in a lower hierarchy. Based on all these relationships, we added three more routing strategies: Short Path, Overhead Balancing and Adoption.
Ø Shortcut Path. A node could not only communicate with its parent or children, but else could talk with its brothers, neighbors and nephews/uncles. Comparing with nearby nodes just communicate with each other via their parent nodes, shortcuts will save lots of energy, increase parent node’s life time and decrease time latency. For wireless sensors, the majority of the energy overhead is consumed by transmitting information, so reduced hops would save node over-head and extend network life cycle.
Ø Overhead Balancing. After nephew relationship was introduced, children nodes could select to send data to their parent node or uncle node based on their energy residual. Energy will be more uniformly distributed between siblings. After received child router’s residual energy, parent node will change his routing table to move some of grandchildren to the other child node, avoiding low residual energy node continuing to be overused.
Ø Adoption. When a parent node was out of life, if all nephews could be accessed by their uncle and the uncle node has enough routing table buffers, nephew nodes could be adopted by uncle node by just changing routing table; instead of recalculating the whole tree address (the depth of the tree is not changed). However, if uncle node is outside its radio coverage or uncle node has no available buffer space, then this node has to communicate with one of its neighbors to obtain new address.
3.2. Naming and Addressing
Naming and addressing lay the foundation of WSNs routing. Naming is to denote a node, while addressing is to locate it in one or multi-hops [10]. DNS is that translation between names and address. There are several methods for address representation. Unique Node Identifier (UID) contains vendor name, product name and serial number, which is too redundant in practical use. MAC address is a unique identifier for each network interface, while this 48bit identifier overhead would be 150% for 4-octed frame. Dunkels Adam etc. [8] presented a spatial IP address assignment mechanism, where sensors construct an IP address using their location information. However with the development of smart cities, the sensor deployment density increases. If there are more and more sensors in an area, the location information will be not so accuracy that different sensors will be assign a same IP, which will raise another problem, Duplicate Address Detection and Address Conflict Elimination, which will complicate naming and addressing. Moreover IP addressing can neither improve address overhead problem. Network identifiers [9] have been added to each person area networks to avoid confusion between different persons, which may share a same frequency. In this paper, THR routing proposal runs on nodes’ identifiers in one sensor network.
Comparing with all different addressing methods, this proposal chose a network address of 12bits (0X000 to 0XFFF). This addressing consumes less resource and is always enough for most WSNs environments.
All the nodes’ initial address is set as 0X000. Coordinator node’s address was set as 0X001. Address block size for a Full Function Node (FFN) is calculated by Equation (1), where d is depth, Cm is maximum children a parent node could have, Rm is maximum router children a parent node could have, Lm is maximum depth of a tree. The FFNs which have received address would search nearby unrecognized node to distribute its address block. Network will allocate network addresses hierarchically in top down manner until all nodes have been assigned an identifier.
(1)
In simulation, after a tree is set, coordination node would send command to set up all the relationships using function packets as shown in Table 1. From the received addresses, this FFN would analyze which node is his brother and which is his nephew and set different routing tables. The relationships could be found by distance vectors, which calculated by address. A node with address of Addr locates in tth branch of TOP node, where,
(2)
Step by step, location of a node in a tree could be calculated. If Cm = 2 and two nodes’ location vectors are [1 2 1] and [1 2 2] respectively, they are brothers. To relay a packet to coordinator, it should at first determine the distance between relay node to its destination. Node would choose the shortest distance node unless it residual energy is under a threshold.
4. OMNet++4.1 Network Simulation
Several simulation platforms are developed on OMNet++ simulator. These simulation platforms are always consisted by tens or hundreds of simulation modules. Researchers could utilize the established simulation modules directly,
![]()
Table 1. Command and data packets structure in enhanced THR routing protocol.
which makes it much easier to issue a simulation. Simulation platforms like PhoenixSim [12] in optical network simulation and Wvsn-model [13] in WSNs simulation. However because of compatibility problems, Wvsn-model is not available for OMNet++4.1. We designed components like transmitter modules, receiver modules and routing modules, and then issued an simulation as shown in Figure 2. The state machine of transmitter module and receiver module is shown in Figure 3 and Figure 4. Routing module just modify the next hop address based on routing table information. These modules could be organized into a basic sensor node. While realizing this one simulation needed in enhanced THR protocol, all modules we developed create a basic WSN simulation platform.
Figure 5 and Figure 6 shows simulation result on OMnet++. Figure 5 shows the comparison of hop numbers and between basic THR routing and enhanced THR routing protocols, while Figure 6 shows packed delay from sensor node to its sink. Both figures show that Enhanced THR would reduce hops from source to sink nodes. Different from AODV, THR do not need to create a link each time to transfer a packet, reduced hops would decrease average time delay from source to sink. In OMNet++ simulation, radio signal coverage is stepwise set as three constants numbers. In a fixed area and constant radiation distance (radiation distance is shown in Figure 4 as white circle around each node), increased WSN nodes density will create a better connected routing tree for both basic THR and enhanced THR routing protocols, so if the reduce of radiation distance can’t neutralize the effect of node density increase, both routing hops and delay will decrease in basic THR and Enhanced THR routing protocols, as shown in Figure 5 and Figure 6.
![]()
Figure 3. State machine of receiver module.
![]()
Figure 4. State machine of transmitter module.
![]()
Figure 5. Comparison of hops and latency between enhanced THR to Basic THR routing protocol.
![]()
Figure 6. Comparison of hops and latency between enhanced THR to Basic THR routing protocol.
5. Testing on TI Instruments
This protocol is designed and simulated on OMNet++4.1, then transplant to TI instruments for P2P test. IAR Embedded Workbench is a set of complete tools including C compiler and debugger. Together with two TI Chipcon SmartRF®04EB boards, we realized temperature sensing and transmitting periodically (Figure 7). We have two boards and set as source and sink. CC2430 integrated a transceiver and a temperature sensor. Temperature sensor generates an analog signal indicating environment temperature, after analog to digital
![]()
Figure 7. Source and sink sensor nodes to test enhanced THR routing protocol.
conversion (ADC), it is converted to a string with accuracy to percentile. This number displays on local LED screen and the receiver’s LED screen after received by receiver node. In this test, source will sense environment temperature and sent to sink node via Enhanced THR protocol every 5 seconds.
6. Conclusion
In this enhanced THR WSN routing protocol, three shortcuts based on social relationships Neighbour, Nephew and Brother, were added into hierarchical tree. And three methods based on these relationships were introduced, which are Shortcut, Overhead Balancing and Adoption. A fully routing protocol simulation is realized on OMNet++4.1 and partly transplant this protocol to TI instruments Chipcon SmartRF04®EB embedded boards. With comparison with basic THR routing protocol, this enhanced THR protocol could distribute energy overhead more uniformly between nodes, which not only improves the latency performance but also extends the whole network’s living time. This enhanced THR protocol would be more efficient on static WSNs environments.
Acknowledgements
This research is supported by China High Technology Research and Development Program (Project Name: Large-scale True Three-dimensional Display Technology. Grant No.: 2012AA011902).