Shortest path algorithm for data transmission in wireless ad hoc sensor networks

Shortest path algorithm for data transmission in wireless ad hoc sensor networks

• 1.
  International Journal ofAd hoc, Sensor & Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 SHORTEST PATH ALGORITHM FOR DATA TRANSMISSION IN WIRELESS AD-HOC SENSOR NETWORKS N. Pushpalatha1, Dr.B.Anuradha2 1Assistant Professor, Department of ECE, AITS, Tirupathi 2Associate Professor, Department of ECE,S.V. University College of Engineering, Tirupathi. ABSTRACT Wireless sensor networks determine probable in military, environments, health and commercial applications. The process of transferring of information from a remote sensor node to other nodes in a network holds importance for such applications. Various constraints such as limited computation, storage and power makes the process of transferring of information routing interesting and has opened new arenas for researchers. The fundamental problem in sensor networks states the significance and routing of information through a real path as path length decides some basic performance parameters for sensor networks. This paper strongly focuses on a shortest path algorithm for wireless adhoc networks. The simulations are performed on NS2 and the results obtained discuss the role of transferring of information through a shortest path. KEYWORDS Sensor Node, Shortest Path algorithm, WSNs (Wireless Sensor Networks), Radio Range. 1. INTRODUCTION Wireless adhoc sensors are being used in various applications and have gained curiosity as well as importance during the last decades. Wireless adhoc sensor network consists of a number of sensors increase across a geographical area, each sensor has wireless communication ability and some level of aptitude for signal processing and networking of the information. Some examples of wireless ad hoc sensor networks also includes military sensor networks (MSN) and wireless observation sensor networks (WSSN).Specific applications like object tracking, vehicle monitoring and forest fire detection rely totally on adhoc networks, since there use, design and exploitation is fixed requiring great amount of stability. Therefore two ways to classify wireless adhoc sensor networks are, (a) whether or not the nodes are independently addressable (b) whether the information in the network is aggregated. The sensor nodes in a parking lot network should be independently addressable, so that one can trace the entire object. In some applications broadcasting of a message is required within all the nodes. Therefore each node in the network is liable and its priority of node placement also becomes important [10]. The above cited theory reflects an important requirement for adhoc networks to ensure that the required data is scattered to proper end users through a genuine and shortest path. The work proposed in this paper shows that adhoc networks can be easily managed and configured for specific use if the routing path is shortest. Sensors can schedule their role more accurately and in time if the connecting path is DOI : 10.5121/ijasuc.2014.5402 13
• 2.
  International Journal ofAd hoc, Sensor & Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 shortest. The reduced path length also improves localization and power consumption for self powered sensor nodes within adhoc networks. Wireless Sensor Networks (WSNs) consists of mobile wireless nodes communicating without the support of any pre-existing fixed communications. Such great WSNs offer vast application perspectives. Sensors are small devices with hardware constraints (low memory storage and low computational resources) that rely on battery. Sensor Networks thus require energy efficient algorithms to make them work properly in a way that their hardware features and application requirements.A low power sensor node has limited transmission power and this can communicate only to limited number of nodes, called its neighbourhood. Multi-hop communications are used to route data from source to destination [8]. 14 2. RELATED WORKS The current interests in sensor networks has led to a number of routing schemes that use limited resources available for sensor nodes to effectively find and resolve to a shortest path for power optimization and an efficient information forwarding scheme. Some of the existing shortest path algorithms are discussed as follows. Many research and performance studies have been made on evaluation and energy utilization. However, there has been only modest research on how the network topology impacts WSN performances. Most of the research on the topic rather focuses on how to efficiently place node on a field to achieve the best performances for given algorithm [11]. 2.1. DV (Distance Vector) Hop localization algorithm In multihop propagation the distance between two or more than two hops is calculated using conventional DV-Hop algorithm [2]. In a sensor network each node whether it is a beacon node or an anchor node as a hop count. The information is processed from one node to another through a hop path, if higher is the hop count of a sink node the information becomes unusable more early, therefore only a minimum level of hop count should be maintained within all useful nodes. This algorithm relies on averaging of hops and is performed to calculate approximately the size of a single hop, upon receiving average size of the hop, left over node multiply the size of the hop with the total number of hop count to calculate the actual distance between two hops as shown in equation 1. Where (xi , yi ), ( xj , yj ) are the coordinates of anchor node i and anchor node j, hj is the hop between beacon node i and beacon node j. The technique facilitates the unknown nodes to receive hop size information, and save time, they transmit the hop size to their neighboring nodes and could assure that the majority of nodes receive the hop-size from a beacon node which has the least hop between them. Lastly unknown nodes compute the distances of the beacon nodes based on hop length. 2.2. LEACH (Low Energy Adaptive Clustering Hierarchy) LEACH [3] is a cluster based routing protocol in which a cluster head collects information from sensor node belongs to a cluster and sends the information to the sink node after the collection procedure. To make all sensor nodes in this network consume their node energy equally and
• 3.
  International Journal ofAd hoc, Sensor & Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 develop the life time of the network, this algorithm at random changes the cluster head, which in turn uses more energy compare to other nodes. To reduce the communication costs, the cluster head does information aggregation and then sends the information to the sink node. The theory is explained through a mathematical relation in equation 2. Where Pt is the desired percentage of cluster heads, r is the current position number, G is the set of nodes that have not been cluster-heads in the last 1/Pt positions. It consists of two phases; a set-up phase and a steady state phase. This algorithm has three postulates that are specifically predecided namely cluster set, cluster node and cluster head, and can seen in fig 1. The cluster head send the aggregated data to the sink node, called its base station. To reduce the slide of the cluster head, many positions of information frame transfer are performed followed by a repeat of the cluster reconfiguration procedure. Since LEACH uses a possibility in selection of cluster heads, its advantage is that all nodes have an opportunity of becoming a cluster head within a network, hence maintaining uniformity. 15 Figure 1: Clusters of LEACH Algorithm 2.3. Greedy Algorithms In this approach whenever a node decides the transmission path based on the position of its neighbors, the source compares the position of the destination with the coordinates of its neighbors and propagates the information to the neighbor which is closest to the final destination. The process is repeated until the packet reaches the deliberate destination. Several metrics related to the concept of closeness have been proposed in this area, among them, the most popular metrics is the Euclidean distance and the projected line joining the relaying node and the destination. In this scheme the unreliable neighbors are not taken into account for the retransmissions. Another geographic protocol for information is discussed SPEED (Stateless Protocol for End-to-End Delay) to calculate approximately the delay of the transmitted packets [4][8]. The major limitation of the greedy algorithms is that the transmission may fail when the current holder of the message has no neighbors closer to the destination except itself. This could occur even when there is a possible path between the two extremes, for instance, when an obstacle is comes into existence. The setup is shown in Figure 2.
• 4.
  International Journal ofAd hoc, Sensor & Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 16 Figure 2: Distance Estimation of Greedy Algorithm Greedy Schedule (S[1..n],F[1..n]): Sort F and permute S to match Count 1 X[count] 1 for i 2 to n if S[i] F[X[count]] count count + 1 X[count] i Return X[1..count] 2.4. SPIN (Sensor Protocols for Information via Negotiation) A family of adaptive protocols, called SPIN [5] is suggested efficiently to broadcast information among sensors in an energy-constrained wireless sensor network. Nodes organization a SPIN communication protocol name their information using high-level information descriptors, called as meta-information. They use meta-information discussions to eliminate the transmission of redundant information throughout the network. The SPIN nodes can base their communication decisions both upon application-specific knowledge of information and on knowledge of the resources that are available to the information. This allows the sensors to efficiently distribute information given a limited energy supply. Four specific SPIN protocols have been analyzed they are, SPIN-PP and SPIN-EC, which are optimized for a point-to-point set of connections, and SPIN-BC and SPIN-RL, which are optimized for a distribution network. In point-to-point networks, the sender announces that it has new information with an advertisement message to each neighbor. When the neighbor receives the information, the node checks the meta-information to know if it already has stored the information item. If the neighbor is interested in the information, it responds with a request memo, upon receiving it, the sender retransmits the information in a information message. The neighbor that receives the message informs about the availability to its own neighbors with an advertisement message. Taking into account the broadcast transmission, the node also responds with just one information message even when it has received multiple request messages. SPIN incorporates some consistency functionalities to keep track of the messages that it receives and its position of origin. This algorithm is also very successful in energy starved WSNs. 2.5. Data Centric Routing Protocol The information centric routing protocol is the first group of routing protocols and discuses some conventional aspects. The SPIN which is a source-initiated protocol [6] does not apply a three stage handshake interface for disseminating information. The source and destination might transmit alternately as follows, request to send, ready to receive, send message, message received
• 5.
  International Journal ofAd hoc, Sensor Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 [7][9]. Meta-information is used to discuss with each other before transmitting information to avoid transmitting unnecessary information in the network. This protocol can be implemented for real time sensor networks. 17 2.6. A Basic Approach towards Problem Formulation The route mapping problem requires a wide area of research, along with an algorithm, pertaining to dissimilar cases. There has been a great research on existing algorithms and suggested approaches for designing a network based on successful path for minimizing energy utilization. The basic problem in this environment relies totally on managing such a path that extensively overcomes and out performs the existing approaches. The algorithm suggested often finds use in applications based on a reasonable and pedagogic approach. The current trend mainly focuses on a probabilistic approach to transfer information from or within nodes deployed to from a self-sustainable wireless sensor network. The work highlighted in the paper shows an approach for transmission of information within randomly placed sensor nodes. It presents a basic technique for analyzing the information transfer between nodes that are deployed to from a WSN. Initially five nodes are positioned in an open environment as shown in fig.3 for sensing the mechanism to route information depends totally on the path and its supportive algorithms. The direction of information transfer is calculated using the position of the node, protocols and the topology. Simulations are performed on NS2 and verification of results are generally discussed in sections to follow. The algorithm is as follows. Step1: Label five nodes Step2: Check information flow between nodes Step3: Check route between node 0 to node 4 Step4: Check information transfer between nodes Step5: Check route between node 1 to node 4 Step6: Check overlap between node 2 and node 3 Step7: If path breaks between node 0 and node 2 find novel path, Step8: Novel path between node 1 to node 2 , If novel path fails, Step9: Ensure again a novel path between node 2 to node 4
• 6.
  International Journal ofAd hoc, Sensor Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 Step10: Ensure information flow between node 2 to node 4, check information flow again 18 Step11: The shortest path is verified for information flow 2.7. Results The information transfer mechanism can achieve between the nodes taking different routes in amount. The prophecy of route is performed over Nam (Network Animator). Nam provides clear prophecy of packet follow between nodes deployed to from a network. Initially the route followed is from node 0 to node 4 as shown in fig. 4 having some amount of time t which equals to 0.5 ns. During second mode of packet forwarding the route starts from node 1 to node 4 as shown in fig. 5 having the previous amount of delay time. It is noted that at the same instance of time t collisions of information packet occurs between nodes 2 and node 3as shown in fig 6, as between node. The route gets break and information flow is intermittent. The key point to be noted is, upon route breaking between node 0 and node 2 and the path breaking between node 1 and node 2. The information flow starts from node 2 to node 4 adaptive in shortest path to promote the information flow in a continuous manner, this can be visualized in fig 7. The simulated results are captured in a trace file of nam as shown in the graphs highlighted in Figure 8. Figure 4: Information Flow from Node 0 to Node 4
• 7.
  International Journal ofAd hoc, Sensor Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 19 Figure 5: Information Flow from Node 1 to Node 4 Figure6: Collisions of Information Packet
• 8.
  International Journal ofAd hoc, Sensor Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 20 Figure 7: Path Break Between One Node to Another Node 3. CONCLUSIONS The results show major role for the values plotted in this graph. The number of nodes and their propinquity can be seen for a shortest path used to transfer information between nodes in an adhoc sensor network. The proposed scheme needs a particular justification and testing before applying to accomplish practical results pertaining to such types of deployments. In the graph x-axis indicates no. of nodes and y-axis indicates time in seconds and blue line show the flow of information. Figure 8: Simulation Results of Nodes Vs Time Plot
• 9.
  International Journal ofAd hoc, Sensor Ubiquitous Computing (IJASUC) Vol.5, No.4, August 2014 ACKNOWLEDGEMENTS The author gratefully acknowledges to Annamacharya Institute of Technology and Sciences for the Environment for funding this work. The author also acknowledges S.V. University College of Engineering for supporting our WSN deployment at the facility. Finally, a thank you goes to the reviewers for their insightful suggestions to improve the quality of this paper. 21 REFERENCES [1] R. Jurdak. “Modeling and Optimization of Ad Hoc and Sensor Networks,” Bren School of Information and Computer Science, University of California Irvine. Ph.D. Dissertation. September, 2005. [2] T. He, C. Huang, B.M. Blum, J.A. Stankovic and T. Abdelzaher, Range Free Localization Schemes for Large Scale Sensor Networks, ACM International Conference on Mobile Computing and Networking, pp.81-95,2003. [3] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, proc. Hawaii International Conference on System Sciences, Vol. 8, pp. 1-10, Jan. 2000. [4] Kulik, J.; Heinzelman, W.; Balakrishnan, H. “Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks”. 8, 169–185. Wirel. Netw.2002. [5] He, T.; Stankovic, J.A.; Lu, C.; Abdelzaher, T.F. SPEED: “A Stateless Protocol for Real-Time Communication in Sensor Networks”. In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), Providence, RI, USA, pp. 46–55. May, 2003. [6] Akkaya, K.; Younis, M. “A Survey on Routing Protocols for Wireless Sensor Networks”. 3, 325–349, Ad Hoc Netw. 2005. [7] Wireless Sensor Networks by F. L. Lewis, http://arri.uta.edu/acs/networks/Wireless Sensor Net Chap04.pdf, 2005. [8] Xing Guoliang, Lu Chenyang, Pless R, Huang Qingfeng. Im-pact of sensing coverage on greedy geographic routing algo-rithms. IEEE Trans. Parallel Distrib. Syst., 2006, 17(4):348{360. [9] Šimek, M.; Komosný, D.; Burget, R.; Morávek, P.; Sá Silva, J.; Silva, R. Data Gathering Model for Wireless Sensor Networks Based on the Hierarchical Aggregation Algorithms for IP Networks. International Journal of Computer Science and Network Security. 2008. 8(11). p.200-208. ISSN 1738-7906. [10] V. Vassiliou and C. Sergiou. Performance study of node placement for congestion control in wireless sensor networks. In Inter. Conf. on New Technologies, Mobility and Security, (NTMS), 2009. [11] Tony Ducrocq, Michael Hauspie, Nathalie Mitton and Sara Pizzi, On the Impact of Network Topology on Wireless Sensor Networks Performances, International Workshop on the Performance Analysis and Enhancement of Wireless Networks(PAEWN)(2014) AUTHORS N.Pushpalatha completed her B.Tech at JNTU, Hyderabad in 2004 and M.Tech at A.I.T.S., Rajampet in 2007. Presently she is working as Assistant Professor of ECE, Annamacharya Institute of Technology and Sciences Tirupati since 2006. She has guided many B.Tech projects and M.Tech Projects. Her Research area includes Data Communications and Ad-hoc Wireless Sensor Networks. Dr.B.Anuradha is working as Professor in the Department of ECE, at Sri Venkateswara University College of Engineering since 1992. She has guided many B.Tech and M.Tech projects. At present Five Scholars are working for PhD. She has published a good number of papers in journals and conferences