Base Station Assisted Routing Protocol For Wireless Sensor Network

Base Station Assisted Routing Protocol For Wireless Sensor Network

Vaibhav Pratap Singh and Harish Kumar

Gurgaon Institute of Technology and Management (GITM) , Gurgaon (Haryana), INDIA

Abstract

A wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. This proposed routing Protocol is based on single base station, so it can be extended to the multiple base station.

1. Introduction to WSN

   The development of wireless sensor networks was originally motivated by military applications such as battlefield surveillance. However, wireless sensor networks are now used in many civilian application areas, including environment and habitat monitoring, healthcare applications, home automation, and traffic control. In addition to one or more sensors, each node in a sensor network is typically equipped with a radio transceiver or other wireless communications device, a small microcontroller, and an energy source, usually a battery. In WSN, hundreds or thousands of sensor nodes are randomly scattered in the sensor field. These nodes sense the data and send this sensed data to the cluster head (in case of hierarchical routing) or directly to the base station according to the cluster head or base station respectively. A directional antenna has been used for localization in wireless networks. In [Directionality Based Location Discovery Scheme for wireless sensor networks], Nasipuri and Li present a localization scheme where three or more directional antennas are used to scan the network in a synchronized manner, and each sensor node computes its location using the angle-of-arrival estimation technique. These papers have a similar objective of reducing the hardware/software complexity of sensor nodes. In BeamStar, a sensor simply receives a control message

   from the base station, which carries its location information. Low-energy adaptive clustering hierarchy (LEACH) is one of the most popular hierarchical routing algorithms for sensor networks. The idea is to form clusters of the sensor nodes based on the received signal strength and use local cluster heads as routers to the sink. This will save energy since the transmissions will only be done by such cluster heads rather than all sensor nodes. Most of the routing protocols for sensor networks require location information for sensor nodes. In most cases location information is needed in order to calculate the distance between two particular nodes so that energy consumption can be estimated.

   A sensor is a type of transducer which uses one type of energy, a signal of some sort, and converts it into a reading for the purpose of information transfer. (See Figure 1) For accuracy in the application a calibration of the sensor and its output information is necessary.

   Figure 1. Typical Mobile Sensor Node

   A sensor node is made up of four basic components:

   1. Sensing unit, usually composed of two subunits: sensors and analog to digital converters (ADCs).

   2. Processing unit, which is generally associated with a small storage unit, manages the procedures that make the sensor node collaborate with the other nodes to carry out the assigned sensing tasks.

   3. Transceiver unit: it connects the node to the network.

   4. Power unit: might use solar cells.

2. Wireless Sensor Networks

   Wireless sensor networks are multi-hop networks where wide range of sensor nodes are deployed to guarantees the network connectivity and cooperatively maintain network connectivity. Wireless sensor networks consist of small battery powered devices with limited energy resources. Once deployed, the small sensor nodes are usually inaccessible to the user, and thus replacement of the energy source is not feasible. Hence, energy efficiency is a key design issue that needs to be enhanced in order to improve the life span of the network. Several network layer protocols have been proposed to improve the effective lifetime of a network with a limited energy supply.

3. Architecture of the Protocol Stack For WSN

   The architecture of the protocol stack used in the wireless sensor networks is shown in Figure 2.

   Figure 2. Protocol Stack for WSN

   This protocol stack combines power and routing awareness, integrates data with networking protocols, communicates power efficiently through the wireless medium and promotes cooperative efforts of the sensor nodes. The protocol stack are made up of physical layer, data link layer, network layer, transport layer, application layer, power management plane, mobility management plane, and task management plane. The physical layer addresses the needs of a robust modulation, transmission and receiving techniques. Because the environment is noisy and sensor nodes can be mobile, the MAC protocol must be power aware and able to minimize collision with neighbors broadcast. The network layer takes care of routing the data supplied by the transport layer. The transport layer helps to maintain the flow of the data if the wireless sensor networks application requires it. The power, movement and task management planes monitor the power, movement and task distribution among the sensor nodes. These planes help the sensor nodes coordinate the sensing task and lower overall power consumption. The power management plane manages how a sensor node uses its power. For instance, the sensor node can shut down its receiver after receiving the data from one of its neighbors. It is to avoid getting duplicated messages. Also, when the power level of the sensor node is low, sensor node broadcasts to its neighbors that it is in low in power and cannot take part in transmitting messages. The remaining power is reserved for sensing. The mobility management plane detects and registers the mobility of the sensor nodes, so a route back to the user is always kept, and the nodes can keep track of who their neighbor sensor nodes are. Therefore, the nodes can balance their power and task usage by knowing this situation. The task management plane balances and schedules the sensing tasks given to specific area. Not all of the sensor nodes in that region are required to perform the sensing tasks at the same time. So, some nodes perform the task more than others depending on their power level. These management planes are need so that sensor nodes can work together in an energy-efficient way, route data in a mobile wireless sensor networks, and share with the resources between nodes.

4. Routing In Wireless Sensor Networks

   A communication network is made up of nodes and links. A link connects two nodes. A communication network carries traffic where traffic flows from a start node to an end node; typically, we refer to the start node as the source node (where traffic

   originates) and the end node as the destination node. Consider now the network shown in Figure 3. Suppose that we have traffic that enter node 1 destined for node 6; in this case, node 1 is the source node and node 6 is the destination node. We may also have traffic from node 2 to node 5; for this case, the source node will be node 2 and the destination node will be node 5 and so on.

   An important requirement of a communication network is to flow or route traffic from a source node to a destination node. To do that we need to determine a route, which is a path from the source node to the destination node? A route can certainly be set up manually; such a route is known as a static route. In general, however, it is desirable to use a routing algorithm to determine a route.

   1. Routing Protocols in Wireless Sensor Networks

      Figure 3. Routing Protocols in WSN

      1. Data-centric protocols: Data-centric promises to combine the applications needed to access data (instead of individual nodes) with a natural framework for in-network processing. In many applications of wireless sensor networks, due to lack of global identification along with random deployment of sensor nodes, it is hard to select a specific set of sensor nodes to be queried. This consideration has led to data-centric routing, which is different from traditional address- based routing where routes are created between addressable nodes. In data-centric routing, the sink sends queries to certain regions and waits for data from the sensors located in the selected regions. Since data is being requested through queries, attribute-based naming

         is necessary to specify the properties of data. SPIN is the first data-centric protocol [19], which considers data negotiation using publish/subscribe notion between nodes in order to eliminate redundant data and save energy. Later, Directed Diffusion has been developed and has become a breakthrough in data-centric routing even though some of its performance and functional characteristics are not entirely understood. Then, many other protocols have been proposed either based on Directed Diffusion or following a similar concept.

      2. Hierarchical protocols: Scalability is one of the major design attributes of sensor networks. A single-tier network can cause the gateway to overload with the increase in sensors density. Such overload might cause latency in communication and inadequate tracking of events. To allow the system to cope with additional load and to be able to cover a large area of interest without degrading the service, networking clustering has been pursued in some routing approaches. The main aim of hierarchical routing is to efficiently maintain the energy consumption of sensor nodes by involving them in multi-hop communication within a particular cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the sink. Cluster formation is typically based on the energy reserve of sensors and sensors proximity to the cluster head. LEACH is one of the first hierarchical routing approaches for sensors networks The idea proposed in LEACH has been an inspiration for many hierarchical routing protocols, such as PEGASIS, TEEN. The hierarchical routing paradigms can progressively prolong the network system lifetime because of its dynamic cluster operation. Also they have the advantages such as distributed property and no global network topology information is needed. However, the single hop assumption makes it not be suitable for WSN deployed in wide area. Another disadvantage is that dynamic clustering brings additional cost, such as the changing operation of cluster header.

      3. Location-based protocols: The idea of location- based protocols is using an area instead of a node identifier as the target of a packet. Any node that is positioned within the given area will be acceptable as a destination node and can receive and process a message. In the context of sensor networks, such location-based routing is evidently important to request sensor data from some region. Since there is no addressing scheme for sensor networks like IP-

         addresses and they are spatially deployed in a region, location information can be utilized in routing data in an energy-efficient way. For instance, if the region to be sensed is known, using the location of sensor nodes, the query can be diffused only to that particular region which will eliminate the number of transmission significantly. Some of the protocols discussed here are designed primarily for mobile ad hoc networks and consider the mobility of nodes during the design. However, they are also well applicable to sensor networks where there is less or no mobility. Three main protocols of this category are SMECN [25], GAF [26] and GEAR [27].

5. PROPOSED ALGORITHM

   Consider a wireless sensor network under which wide range of sensor are have been deployed to guarantee the network coverage. The foundation of the proposed algorithm lies in the realization that the base station is not energy constrained node with a large amount of energy supply. Thus, Base-station assisted routing protocol exploits the base station with directional antenna. In the proposed protocol, the following assumption are to be considered.

   1. A fixed base station is located away from the sensor nodes.

   2. The range of sensor nodes can cross the neighbouring region.

   3. The sensor nodes are energy constrained with a uniform initial energy allocation.

   4. Each node senses the environment at a fixed rate and always has data to send to the base station

   5. All sensor nodes are static in position.

   When there is an event occurred over the network, all the sensors have to report the sensed data hop by hop and reaches near to the base station.

   Figure 4 Sector made by power controlled directional antennas

   Sensor data must be associated with location and time that is, where and when the event was first detected to make it usable. This requires efficient localization and synchronization schemes, in addition to a routing protocol that will deliver data back to a base station. Message exchanges for localization, synchronization, or maintaining a routing table or high requirements on a sensor node (for example, CPU, storage, or memory) which will not help in reducing the size and cost of a sensor node. We assume that the base station is not energy constrained and is equipped with a directional antenna with power control capability. With such a directional antenna, the covered area of each base station transmission is a sector. The radius of the sector R is determined by the transmit power, whereas the span of the sector is determined by the beam width of the directional antenna as shown in Fig. 6.1. We assume that the base station can adjust its transmit power to reach all nodes in the network. When an event has occurred in the network, the event is identified by the sensor (sensor closest to the event) is the good idea. The event also be identified by many of the sensors, so have to reduce unnecessary redundant. This requirement can be implemented by having each sensor set a timer upon detecting an event, where the time-out value is set to be inversely proportional to the detected signal strength. Therefore, among all the neighboring sensors that have detected the same event, the sensor with the highest signal strength will time out first and broadcast the corresponding report to its neighbors. Sensor packet format has got the below items:

   BaseID – This is the identifier of the destination base station (in the case of multiple base stations).

   SourceID – This is the 2-tuple identifier, that is,

   {SN;RN}, of the source sensor node.

   LastRelayID – This is the identifier of the last sensor node that forwarded this report.

   Timestamp – This is the time instance when the event was detected (set by the source node).

   The proposed protocol operates in two phase:

   Phase I : Setup phase

   Initially, The base station broadcast an START message to all the sensors in the sensor field, to acquire the neighbor list and it will be used as a forwarding rule for the sensor while routing the data and also it can easily synchronize the local time or clock with the base

   station. To determine the position of the sensor node with respect to the base station, the base station scans the entire region using different transmit power levels. In other words, the base station sends control messages containing the current directionality information and the transmit power level (indicating the relative distanc between the sensor and the base station) through successive scans of the network. A nodes location is thus determined by the directionality of the last base station transmission (called Sector Number SN),as well as the lowest power level that it can receive from the base station (called Ring Number RN ). We therefore define the ID of a sensor to be the 2-tuple

   {SN ; RN}.

   The BaseID field reveals the identification of the base station, which will be useful when multiple base stations are used. The SN field carries the index associated with the direction of the current transmission, and RN is the index associated with the current transmit power. The field SeqNum is the sequence number of the current scan. Additional control information can also be carried in the packet. The base station transmits to the first region (shaded area) by adjusting its phase angle and transmit power as shown in Figure 5.

   Figure 5 Sector and Ring with different transmit power level

   During this transmission, the directional antenna broadcasts a message with {SN;RN} ={1; 1} to all nodes within this region. Sensors located in this region will then obtain their ID as {SN;RN}= {1; 1} as shown in Fig 6.2 (a). Subsequently, with other figures as above, the base station adjusts its transmit power to the next higher level and broadcasts a message with location information {SN;RN}= {1; 2}. Those sensor nodes that have acquired ID {1; 1} from the earlier transmission will not change their ID. All other nodes covered by the second transmission will store this ID, that is, {SN;RN} ={1; 2}, to represent their geographical locations.

   By repeating this procedure, all sensor nodes can derive their IDs (that is, location information) via receiving broadcast control messages from the base station. When a sensor k receives multiple control messages with the same SeqNum, its ID is chosen as below:

   SNk = max{SNi | i { rcvd ctrl msgs with SeqNum} RNk = min {RNi | i { rcvd ctrl msgs with SeqNum}

   After receiving the start START message, each node broadcasts the hello message HELLO to know its neighbor.Each node receiving hello message HELLO sends REPLY message containing its ID, SectorNumber(SN), RingNumber(RN).When a node gets reply, it will note down the ID, SN, RN of the node from where the reply has been acknowledged. In this way each node will have their individual neighbor list. After receiving the information about their neighbors the nodes, for which the base station is within their range, sends a STATUS message to the base station. This STATUS includes ID, Neighbor list of the node. Base station sends an acknowledge (ACK) to all sending nodes. After acquiring acknowledge ACK, the nodes set their level to one which was initially zero and broadcasts a gateway advertisement GW_ADV to all its neighbors. Nodes receiving GW_ADV will check their level. If a nodes level is zero (i.e. a node has not sent their status yet) it sends their STATUS to the node advertising gateway. In this case, a node can receive a GW_ADV from many of the nodes but it will reply only to that node from where it has received GW_ADV message first. Since the nodes, for which the base station is within the range, can send their data directly to it. For such types of nodes the base station is assigned as their cluster head.Each node keeps the IDs of other nodes which are of having the same {SN, RN} from REPLY message and they will form clusters as shown in Fig 6.3. Cluster heads change randomly over

   time in order to balance the energy dissipation of nodes. This decision is made by the node choosing a random number between 0 and 1. The node becomes a cluster head for the current round if the number is less than the following threshold:

   Otherwise, this report has already been forwarded before and will thus be dropped.Suppose that an event is detected by a sensor in a region with ID {2, 3}. The protocol can be easily extended to support multiple base stations for larger sensor networks. A sensor node within the ranges of multiple base stations will choose a unique ID for itself based on messages from each of

   T(n) =

   1 ( 1)

   0

   these base stations.

   When the sensor detects an event, it can simply choose the closest base station (by comparing the RNs of its multiple IDs) to send the report. An intermediate sensor node, after receiving the report, will first check

   where p is the desired percentage of cluster heads (e.g. 0.05), r is the current round, and G is the set of nodes that have not been cluster heads in the last 1/p rounds.

   Phase II : Routing Phase

   Cluster head broadcasts cluster information that includes the IDs of the cluster head. Every cluster head informs each one of its cluster nodes when it can transmit, according to the TDMA schedule which is broadcasted back to the nodes in the cluster. Each cluster head receives the data from its cluster nodes. When all the data have been received, each cluster head performs signal processing functions to aggregate the data it has received along with its own data into a single composite message. This composite signal also contains the ids of the nodes. After each cluster head has created its aggregate message, it forwards it to the base station, either directly (if this is possible) or via intermediate upper level cluster heads The moment it receives a report, the cluster head makes forwarding decisions by making two comparisons. If the last relay of this report is from a different region, it will first compare the reports LastRelayID value with its locally stored forwarding rules, which are set by the base station. The forwarding rules contain one or more IDs of its neighboring regions, for example,

   { {SN;RN +1}, {SN+1;RN}, {SN-1;RN} }

   If no match is found, this report will be dropped. If a match is found (or the last relay is from the same region), the sensor will make a second comparison by searching the signature of the received report in Lk. If no match is found, the new signature will be inserted into Lk (the oldest signature may be discarded from Lk if the list is full), and this report will be rebroadcast.

   the BaseID value in the report header (which was set by the source node). Then, the node makes a comparison and drop/forward decision using its ID and forwarding rules associated with the chosen base station.

6. Conclusion and Future Work

Presented protocol a novel base station-based routing protocol for wireless sensor networks. The proposed protocol was motivated by reducing hardware and software complexity at a sensor node so as to achieve size and cost reduction.

The main idea is to shift some of the communication and processing intensive functions from sensor nodes to the base station. Specifically, we exploited the capabilities of directional antennas and power control at the base station to assist localization, synchronization, routing, and (potentially) many other complex tasks. As a result, the functions of each sensor node can be made much simpler than existing approaches, enabling considerable cost and size reduction on sensor nodes.

We found that the proposed protocol achieves higher reliability at comparable energy cost as compared to a representative core-based routing approach. Therefore, the protocol represents a viable approach to deliver similar or better performance while enabling a much simpler hardware and software design (and thus size and cost reduction) at sensor nodes.

REFERENCES

1. H. Takagi and L. Kleinrock, Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals, IEEE Trans. Comm., vol. 32, no. 3, pp. 246-257, Mar. 1984.

2. T. Hou and V. Li, Transmission Range Control in Multihop Packet Radio Networks, IEEE Trans. Comm., vol. 34, no. 1, pp. 38-44, Jan. 1986.

3. C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, Directed Diffusion for Wireless Sensor Networking, IEEE/ACM Trans. Netwoking, vol. 11, no. 1, pp. 2-16, Feb. 2003.

4. W. Ye, J. Heidemann, and D. Estrin, Medium Access Control with Coordinated Adaptive Sleeping for Wireless Sensor Networks, IEEE/ACM Trans. Networking, vol. 12, no. 3, pp. 493-506,June 2004.

5. X. Ma, M. Sun, G. Zhao, and X. Liu, Improving Geographical Routing for Wireless Networks with an Efficient Path Pruning Algorithm, Proc. IEEE Conf. Sensor, Mesh and Ad Hoc Comm. And Networks (SECON 06), pp. 246-255, Sept. 2006.

6. G. Durgin, T. Rappaport, and H. Xu, Measurements and Models for Radio Path Loss and Penetration Loss in and Around Homes and Trees at 5.85 GHz, IEEE Trans. Comm., vol. 46, no. 11, pp. 1484-1496, Nov. 1998.

7. H. Xu, R. Boyle, T. Rappaport, and J. Schaffner, Measurements and Models for 38 GHz Point-to-Multipoint Radiowave Propagation, IEEE J. Selected Areas in Comm., vol. 18, no. 3, pp. 310-321, Mar. 2000.

8. Shashidhar, Ravi Prakash, Milind Dawande Hop- Constrained Energy-Aware Routing in Wireless Sensor Networks IEEE/ACM Trans. Wireless Communication, pp. 3112-3116, 2005.

9. J. Wieselthier, G. Nguyen, and A. Ephremides Energy- Limited Wireless Networking with Directional Antennas: The Case of Session-BasedMulticasting, Proc. IEEE INFOCOM, pp. 190-199, June 2002.

10. A.Spyropolous and C. RaghavendrA Energy Efficient Communications in Ad Hoc Networks Using Directional Antennas, Proc. IEEE INFOCOM, pp. 23-27, June 2002.

11. ShijinDai, Xiaorong Jing, Lemin Li Research and Analysis on Routing Protocols for Wireless Sensor Networks IEEE Trans. Comm., pp. 5-9, June 2007.