Energy-Efficient Bootstrapping Protocol for Sensor Networks
Rajesh Mathew and Mohamed Younis
Dept. of Computer Science and Elec. Eng.
University of Maryland Baltimore County
Baltimore, MD 21250
and
Abstract
Sensor networks are poised for increasingly wider uses in many military and civil applications. We present a bootstrapping protocol for a class of sensor networks in which the network has high-energy entities called gateways apart from the low-energy sensors. Most research activity in the field of sensor networks focuses on organizing the network and then proceeds to look for energy saving. However, we argue that bootstrapping done inefficiently can be a major source of energy wastage. We present an energy-aware mechanism for initializing the network. Our proposed approach focuses on avoiding collisions in the bootstrapping phase and stresses on keeping receiver/transmitter units off whenever possible to preserve energy. In addition, our mechanism synchronizes the sensor nodes to the gateway’s time base so that TDMA based communication can be used. We study the performance of our mechanism using simulation and compare it to the performance of a basic approach in which sensor nodes have to keep their receivers ON throughout the bootstrapping process, and show the scalability of our system as compared to such approaches.
Keywords: Sensor networks, Network bootstrapping, Energy-efficient protocols, and Energy-Aware Communication.
1. Introduction
Sensor networks are poised to play an important role in a wide variety of military and civil applications. With the aid of sensors, such applications can be accomplished with limited human intervention. For instance, a military reconnaissance can be done remotely using scattered low-energy sensing devices in the zone where targets are expected to move and thus data can be gathered from hostile environments at low cost and minimal risk. Sensor nodes are usually equipped with short-haul radios and powered using very low capacity batteries. In these devices, communication accounts for a major portion of energy usage. Therefore, energy efficient communication protocols are required for sensor networks in order to enhance network’s robustness and extend system’s lifetimes [1].
Typically, a set of sensors is spread throughout an area of interest to detect and possibly track events/targets in this area. The sensing element of a sensor probes the surrounding environment. After performing signal processing of the observed data, sensors communicate this data to a command center usually through a relay or a data concentrator called the gateway. A gateway node is capable of long haul communication and has richer energy resource compared to he sensors. The gateway can perform a host of other tasks such as arbitration of medium access and generating routing tables [2]. Due to scalability requirements and to avoid overloading the gateway, network clustering is recommended through the involvement of multiple gateways, as shown in Fig. 1. Clusters are formed such that its gateway is located within the communication range of all of its cluster sensors.
Prior to network clustering, sensors and gateway nodes need to be informed about the presence of each other. Bootstrapping the sensor network refers to the discovery of deployed sensors and establishing direct communication links between each gateway and sensors that are reachable to it. Bootstrapping can be very challenging while dealing with sensor networks because human intervention to setup and administer the network is not possible in a major portion of the applications that sensors are used for. In addition, as we elaborate in sections ahead, inefficient bootstrapping protocols can eat up a substantial portion of the very limited sensor nodes’ energy. Moreover, time lag between the deployment of sensors and gateways implies that the sensors can waste considerable energy by turning the receiver on and waiting for a message from any gateway.
Fig 1: Multi Gateway Clustered Sensor Network
In this paper, we present an energy-efficient and scalable bootstrapping protocol for sensor networks. The goal of our protocol is to minimize the time spent by the sensor nodes in RECEIVE or TRANSMIT modes so as to achieve maximum energy saving. Unlike approaches where the nodes contend for channel access in the bootstrapping phase, the proposed approach allows sensors to activate their receiver periodically for very short duration. At the end of bootstrapping each gateway should know the set of reachable sensors and synchronize their clock with its own clock. Clock synchronization enables the use of a time-multiplexed model of communication, such as TDMA. TDMA medium access control has been shown to be very energy efficient and thus is a preferred mechanism for sensor networks [3].
In the balance of this section we summarize the related work. Section 2 describes the energy-efficient bootstrapping protocol. Description of the simulation environment and validation of the experiments can be found in section 3. Finally section 4 concludes the paper and discusses our future research plan.
1.1. Related Work
Energy constraints distinguish sensors networks from other wireless communication networks. Therefore, energy efficiency and awareness have been the focus of a lot of research work on sensor networks, such as energy aware routing [2][4], sensor coordination [5], and energy saving through activation of a limited subset of nodes [6]. However most of such research does not pay attention to energy efficiency in the bootstrapping phase.
Time-based bootstrapping of sensor networks has been studied in [7]. The approach relies on sensors to discover each other recursively until discovering a user node. The schedule within a frame is fixed and includes slots for all type of communication. A recently powered-up sensor will listen to traffic to find neighbors and engage with them in order to join the network. Gradual increase in transmission range strategy, incremental shouting, is applied in [8] for sensors discovery. Every node sends announcement messages with an increasing energy to explore the neighborhood. Close sensors, which hear such announcement message would acknowledge the message and indicate their location. The process is repeated by every sensor and would stop when every sensor knows a preset number of neighbors and considers them its group. A group can take on sensing tasks and arbitrate the load among the members. The same approach is applied to groups in order to form a network topology. Such published approaches are so complicated that it may consume lots of energy. In addition there is no clear termination condition, which makes their convergence doubtful.
Approaches for sensor discovery and location determination have been suggested in [9]. The basic idea is to use beacons to make the presence of a sensor known to its neighbors and use multi-lateration to estimate the relative location. Absolute location can be calculated with the availability of reference sensors that are either hand-placed or equipped with GPS. We assume that every sensor knows its location although we would like to explore such ideas as a complimentary procedure to our proposed bootstrapping algorithm.
Energy saving through the use of time-based MAC in wireless sensor networks was explored in [3][10][11]. The idea is to schedule when to activate the radio receiver so that it can be turned off when not expected a message. Turning off the receiver has been shown to achieve saving of up to 70% in energy consumption [10]. Approaches for determining when to turn off the receiver varies. While slots are prescheduled in [11], the decision for deactivating the receiving circuit is made autonomous in [10] by probing the environment. Reservation-based approach for scheduling medium access is pursued in [3]. Nodes make a request to a base station, which responds with a traffic control message indicating medium access schedule. Nodes not included in the traffic control message can turn off their receiver. However, all published mechanisms address normal network operation and do not investigate the potential of TDMA for the bootstrapping process.
In addition, mechanisms that delve into the bootstrapping process such as in [13] assume that the sensors come up and hear a broadcast from a cluster-head. Such an assumption could be impractical since it may not be feasible for all the entities in a sensor network to be deployed at exactly the same time instant. Hence, in a practical deployment, it is possible that the gateway sends out an announcement and the nodes are deployed after this announcement is over. Hence the nodes will not hear this and will continue waiting for an announcement. Therefore, we propose that a complete bootstrapping protocol should have a repetitive structure in which the gateways will send out announcements repeatedly followed by periods in which the sensors can send in their replies.
Thus the areas in which our bootstrapping protocol attempts to improve on existing bootstrapping mechanisms are:
i) Reducing the receiver ON time during the bootstrapping phase by introducing synchronization during this phase after the sensor has heard the gateway’s announcement
ii) Accounting for late sensor deployments by having a repetitive mechanism to add sensor nodes which wake up after the gateway has finished its first announcement and
iii) Reducing power consumption due to the receiver being ON for long periods if the gateway is deployed after the sensors are deployed.
2. Network Bootstrapping
When sensors keep their receivers active after deployment, network bootstrapping can be simply performed by requiring the gateways to send out an announcement. Such a simple scheme has one of the gateways transmit information comprising an announcement about its presence and is followed by the sensor nodes replying. The nodes have no sense of slots or time multiplexing and hence come up randomly and, if no one else is transmitting, send in a reply. This can be a very energy inefficient scheme requiring the sensors to keep their receivers ON till they send in their replies, Further, if the gateway is deployed a while after the deployment of sensors, the scheme becomes very inefficient, as the sensors now keep their receivers ON till the gateway sends out an announcement, and then again till the sensor itself manages to transmit a reply. In fact significant time lag between the deployment of gateways and sensors risk the depletion of sensors energy reserve and thus making the whole network useless.
On the other hand, our approach does not assume that sensor receivers to be active till they send in their replies. Upon deployment sensors switch to a low-energy sleep mode and turn their radio off. Periodically sensors turn on their receiver for a very short duration. Once deployed, gateway nodes will establish communication links among themselves and negotiate ordering for transmitting announcement messages to the sensors. Since sensor nodes are not assumed to be in the RECEIVE mode when the gateway transmits, we do not assume that all the sensors detect the gateways first announcement and hence provide a repetitive structure whereby the gateways announce their presence at regular intervals. In addition, such repetitive structure allows the handling of late sensor deployments. Thus we have the concepts of frames and super-frames, as shown in Fig 2. A frame can be defined as a unit of time when one particular gateway sends out transmissions announcing its presence and solicits replies, followed by the nodes replying. A set of G frames, where G corresponds to the number of gateways in the system can be defined as a superframe if and only if, for every i, 1<= i <= G, Framei corresponds to gateway “i” in the ordered sequence of gateways.
Fig. 2: Frames and Super-frames
The bootstrapping procedure is divided into the following three phases in each frame as shown in Fig 3.:
i) An Announcement Phase - For the gateways to announce their presence and to solicit responses.
ii) A Reply Phase – For sensor nodes to reply back to the gateways and to report their location.
iii) SYNC/CON Phase – includes synchronization bit sequence and control instructions to the sensor nodes.
Fig. 3: Phases in a Frame
A node that sends in a reply successfully in one super-frame does not reply when any other gateway sends announcements, but all the gateways that heard the node’s reply could tabulate this information along with the reply strength as this might be used for clustering. Super-frames keep repeating till no gateway receives a reply in one superframe and this is taken as the termination condition for our algorithm. The number of super-frames needed for the bootstrapping depends on the number of sensors and on the quality of sensor-to-gateway communication links.
2.1. Announcement Phase
Each announcement phase further consists of n1 messages where the gateway reaches out for the sensors n1 times. Fig. 4 shows an announcement phase and the pieces of information involved.
Fig. 4: An Announcement Phase
For a node to send in a reply, the following information is included:
i) Synchronization bits: Before the gateway supplies any information, it will need to transmit a few bits for allowing sensor to synchronize their clock. Clock synchronization enables the sensor to recognize packet boundaries. The size of the synchronization bit sequence depends on encoding of transmitted data. The sequence should be unique to avoid misinterpretation. We shall return to this shortly, after discussing the reply phase. Assume that n3 bits are needed for clock synchronization.
ii) Number of remaining announcement slots: This will tell the node how many more slots exist before it can try to send in reply. This prevents the sensor nodes from replying before the gateway concludes its announcements. For n1 slots, log(n1) bits will be needed.
iii) Number of reply slots: It is necessary for the sensors to know up to what instant a reply could be sent in. Informing the sensors about the number of reply slots, gives the gateways a flexibility for dynamically changing the number of reply slots from frame to frame, possibly depending on the number of sensor nodes yet to reply. Assuming that the number of reply slots is n2, the maximum number of bits required is log(n2).
Thus, the total number of bits in an announcement “a” is a = n3+ log(n1) + log(n2)
2.2. Reply Phase
Fig. 5: Reply Slot – Node sends information to Gateway
The sensor nodes, which listen to any of the gateways’ broadcasts recognize the announcement upon seeing the sequence of ones and further get the number of announcements and reply slot. After the end of the announcements, sensor nodes try to reply sending in their identifications and geographical coordinates in order to register themselves with the gateway. Each replying sensor broadcasts its registration message to cover the maximum of its reachable communication range, hoping for the message to be heard by the largest possible number of gateways. Our work can be extended so that the strengths of the signal of received replies and eliminate the need for GPS through using multi-lateration to estimate the sensor positions. In fact, the actual data transmitted by the sensor in its reply, depends on the protocols used in conjunction with out protocol. For instance, if trilateration is used to estimate sensor positions, the nodes might not send their position information to the gateways.