ISSN : 0975-3273
EISSN : 0975-9085
PHEGADE S.G.1*, PATIL S.A.2*, OZA T.H.3*
1G.H. Raisoni Institute of Information Technology, Jalgaon, MS, India.
2G.H. Raisoni Institute of Information Technology, Jalgaon, MS, India.
3G.H. Raisoni Institute of Information Technology, Jalgaon, MS, India.
* Corresponding Author : tejalhoza@gmail.com
Received : 21-02-2012 Accepted : 06-03-2012 Published : 15-03-2012
Volume : 4 Issue : 1 Pages : 87 - 90
Adv Comput Res 4.1 (2012):87-90
Conflict of Interest : None declared
Wireless Sensor Network (WSN) is an emerging technology that shows great promise for various futuristic applications both for mass public and military. A wireless sensor node consists of sensing, computing, communication, actuation, and power components. These sensing devices have the opportunity of collaboration amongst themselves to improve the target localization and tracking accuracies. Distributed data fusion architecture provides a collaborative tracking framework. Due to the present energy constraints of these small sensing and wireless communicating devices, a common trend is to put some of them into a dormant state. The problem of obtaining a minimum cost topology for a wireless sensor network given matrices specifying the cost of links between all pairs of nodes and the internodes requirements is considered. This paper discusses the optimizing strategy for routing and selecting optimum number of nodes using MENTOR algorithm. In this we find the path with minimum cost between numbers of nodes in the network. It is closely related to decision on what speed links to use and how to route traffic through the network.
sensor, wireless, dormant states, data fusion architecture, MENTOR, backbone node, median.
Wireless sensor network [4] was developed from common sensors that are able to enhance the practical side, flexibility, and mobility of a sensor. With a wireless sensor, the sensor could be placed in a Hazardous Area, and difficult area.
Wireless Sensor Network (WSN) is a wireless network consisting of multiple sensors (sensor nodes) is placed in place - a different place for monitoring the condition of a plan. Wireless sensor network consists of a microcontroller system that has a sensor unit and a transceiver unit (transmitter and receivers), transmitters and receivers to transmit data to receive data. The sensor is useful to investigate the extent to which the error between set point and the value of the sensing to the control system. Following figure 1 [4] shows that how sensor are spread over the network and how the data is access from sink node through network.
Sensor networks are composed of a large number of small nodes with sensing, computation, and wireless communication capabilities. In sensor networks, sensor nodes are usually scattered and the position of sensor nodes needs not be predetermined. It means that sensor network protocols and algorithms must provide self- Organizing capabilities. Another feature of sensor networks is the coordination of sensor nodes to produce high-quality information about the sensing environment.
The features of sensor networks provide a wide range of applications such as health, military, and home. The realization of these and other sensor network applications require wireless ad-hoc networking techniques. Although many protocols and algorithms have been proposed for traditional wireless ad-hoc networks, they are not well suited to the unique features and application requirements of sensor networks. Therefore, many routing and data dissemination protocols should be designed for sensor networks.
Wireless sensor networks consist of individual nodes that are able to interact with the environment by sensing or controlling physical parameters. These nodes have to collaborate. As shown in [Fig-2] [1] , the wireless sensor network infrastructure of the standard components like sensor nodes, gateways, Internet, and satellite link, etc. to fulfill their tasks. The nodes are interlinked together and by using wireless links each node is able to communicate and collaborate with each other.
Sensor nodes are the network components that will be sensing and delivering the data. Depending on the routing algorithms used, sensor nodes will initiate transmission according to measures and/or a query originated from the Task Manager. A basic sensor node typically having five main components which are shown in [Fig-3] [1] . They are controller, memory, sensors, communication device and power supply.
A controller is to process all the relevant data, capable of executing arbitrary code. Memory is used to store programs and intermediate data. Sensors and actuators are the actual interface to the physical world. These devices observe or control physical parameters of the environment. The communication device sends and receives information over a wireless channel. And finally, the power supply is necessary to provide energy.
A gateway which is high performance, high reliability, low-power and expandable is designed to connect WSN with external network. Gateway accepts data collected by wireless sensor network and then stores the data in an embedded database. And users can manage the data via a website from long-distance or applications in console terminal. The users or task managers on the Internet can access the data of the sensor networks flexibly via web services. Each node in the WSN has a unique IP as its identifier, and it can be accessed by the IP directly.
A wireless ad hoc sensor network consists of a number of sensors spread across a geographical area. Each sensor has wireless communication capability and some level of intelligence for signal processing and networking of the data. Some examples of wireless ad hoc sensor networks are the following:
1. Military sensor networks to detect and gain as much information as possible about enemy movements, explosions, and other phenomena of interest.
2. Sensor networks to detect and characterize Chemical, Biological, Radiological, Nuclear, and Explosive (CBRNE) attacks and material.
3. Sensor networks to detect and monitor environmental changes in plains, forests, oceans, etc.
4. Wireless traffic sensor networks to monitor vehicle traffic on highways or in congested parts of a city.
5. Wireless surveillance sensor networks for providing security in shopping malls, parking garages, and other facilities.
6. Wireless parking lot sensor networks to determine which spots are occupied and which are free.
7. Health applications
Tele-monitoring of human physiological data. Tracking and monitoring patients and doctors inside a hospital, Drug administration in hospitals.
These applications shows that it may be necessary broadcast a message to all the nodes in the network. If one wants to determine the temperature in a corner of a room, then addressability may not be so important. Any node in the given region can respond. The ability of the sensor network to aggregate the data collected can greatly reduce the number of messages that need to be transmitted across the network.
Network topology is derived from the physical neighborhood, so we must determine which topology gives the optimal number of neighbors that a node can handle to transmit to or receive from since, we are dealing with three dimensional in physical world & thus restricted in choice of topologies. In this paper, the question we are seeking to answer is what is the best topology and routing for a wireless network of sensors. Hence the Mesh Network Topology Optimization and Routing (MENTOR) algorithm is suggested for finding the optimized topology and routing of the hops.
In selection of WSN topology, the objective is to determine which locations to directly connect. It is closely related to decision on what speed links to use and how to route traffic through the network. In WSN topology optimization problem is clearly difficult. For practical size of the network, virtually all approaches have been heuristics. There are many algorithms which suggest topologies for mesh WSN.
The MENTOR algorithm [2] is appropriate for the design of many types of communication network because it does not rely on the characteristics of any particular networking technology or architecture but on basic design principles. Mentor algorithm begins by finding a center of mass C for the network. This C is defined as the node which minimizes the quantity.
Where cij is the cost of connecting nodes I and j and wij is the weight of node j defined to be the total requirements to and node j that is,
Median is the node that is best suited for the traffic.
The next step is to identify the backbone network nodes. For backbone node identification, threshold algorithm can be used. Using threshold algorithm, the threshold on node weight wj is calculated (W).
Any node, whose weight exceeds threshold (W), is selected as a backbone node.
Next given R a parameter which specifies a radius of cost around backbone node which is calculated as selecting maximum cost weight node in selected topology.
All nodes lies in the range of R declared to be local nodes. After completion of this process, all nodes in the network are either backbone node or local node.
Next, a tree is formed to interconnect the nodes in network shown in [Fig-4] [2] . This tree has following characteristics:
1. It is a spanning tree on the backbone nodes. Each local node is connected directly to the closest (in terms of cost) backbone node.
2. The tree has short links i.e. MST.
3. The paths in the tree are short i.e. Shortest Path Tree.
If the tree is formed with all these characteristics then there is a possibility of creating a network which satisfies the following objectives
1. Requirements are routed on relatively direct paths.
2. Links have a reasonable utilization. The utilization should not be so high that it suffers from loss or delay and it should not be so low that the link is not cost effective.
3. Relatively high capacity links are used.
This problem can be approached with a heuristic [2] which can be thought of as a modification to both Prims and 0020 Dijkstra’s algorithm. Prim’s and Dijkstra’s MST and shortest path trees are identical.
In Prim’s algorithm start at a designated node I and attempt to label other nodes, j, with
Lj = dij
Where dij is the distance (or cost) between nodes i and j. This selects trees with short links.
In Dijkstra’s algorithm nodes are labeled with
Lj= Li + dij
This selects tree with shortest path. A hybrid algorithm can be created by labeling nodes with
Lij = αLi + dij
Where α is between 0 or 1. For α = 0 this is Prim’s algorithm and α = 1 this is Dijkstra’s . The larger α, more attention is given to path length. When the triangle equality holds i.e when the cost of a link (A, B) is no greater than the sum of the costs of links (A,C) and (C,B) for all A, B, C when α is 1 we get a star centered at the median.
Node pairs have to be considered for direct connection in an order that allows overflow traffic (traffic that cannot be carried on the direct routes) to be added to the traffic of a node pair that has not yet been considered for physical connection. This is achieved by a topological sorting of the nodes.
Suppose consider the WSN nodes as shown in figure 5, the path is a set of two pairs of nodes (O,H) and (H,D), where (O,D) is the original pair and H is a detour node. H is chosen as the predecessor of either O or D in the shortest path tree. The choice is made by finding an H that minimizes the quantity cOH + cHD. The number of dependencies of a pair (O,D) is now defined as the number of (O,H) pairs and (H,D) pairs that coincides with the pair (O,D) [5] .
Topological sorting starts by adding all node pairs that have no dependencies to a set. Now all dependencies of the remaining nodes that resulted from alternative paths on the pairs that have been added to the set are removed. This will result in more node pairs having no dependencies, and those nodes are also added to the set. This process is repeated until all node pairs are in the set.
Different algorithms are available for selecting optimal number of nodes. So instead of MENTOR algorithm we can use other algorithms to get more correct result. We can apply artificial neural network to train the nodes for selecting optimal number of nodes.
A good network topology is not only efficient in terms of traffic flow; it must be robust. If removing a single link or node from a network results in the partitioning of the network into separate parts, the network is vulnerable. Thus if such a physical link or node would fail, communication would become impossible for certain node pairs.
MENTOR usually generates networks that are robust, but no guarantee is given that more than one independent path exists between each node pair. Hence we further used more efficient technique to find out physical location of nodes in wireless sensor network to apply best topology for communication.
Wireless sensor network are increasingly being used in military, environmental, health and commercial application. Sensor networks are inherently different from traditional wired networks as well as wireless ad-hoc networks. As the nodes in WSN are physically distributed to find optimal number of nodes is one of the challenge. So the main focus of this paper the MENTOR algorithm is discussed and how this can be applied to WSN. MENTOR provides a fast, efficient way of determining a good construction for a physical network. Although its solution is a heuristic, the speed of the algorithm allows it to be included in network planning tools. Some of its input parameters can be manipulated while the resulting network is continuously visualized in real time. If this algorithm is applied to WSN, it is possible to get optimal number of nodes related to cost and weight of nodes. This node then communicates to each other by calculating paths with minimum weights by using Prims & Dijkstra’s algorithm.
[1] Miguel Angel Erazo Villegas, Seok Yee Tang, Yi Qian “Wireless Sensor Network Communication Architecture for Wide-Area Large Scale Soil Moisture Estimation and Wetlands Monitoring†University of Puerto Rico at Mayagüez Walsaip Research Project.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[2] Kershenbaum A., “Telecommunications Network Design Algorithms†Tata McGraw Hill.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[3] Jamal N. Al-Karaki Ahmed E. Kamal “Routing Techniques in Wireless Sensor Networks: A Survey†Iowa State University, Ames, Iowa 50011.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[4] monet.postech.ac.kr, Mobile Networking Laboratory Computer Science and Engineering, Pohang University of Science and Technology.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[5] Botha M., Zuurmond G.J. and Krzesinski A.E. “An Implementation of the MENTOR Algorithm for Random Network Generation†_ Department of Computer Science University of Stellenbosch.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
 | Fig. 1- Wireless Sensor Network |
 | Fig. 2- sensor network and infrastructure |
 | Fig. 3- Sensor Node Architecture |
 | Fig. 4- Spanning tree for MENTOR |
 | Fig. 5- WSN Nodes |