Localization is a significantly vital research issue in wireless sensor networks (WSNs) which mainly focuses on static sensor networks. Mobile sensors that are used to enlarge a sensed area depict the importance of designing a localization scheme in mobile sensor networks. This paper is a proposal of two schemes which increases the accuracy of localization in the previous scheme. First scheme is that, the normal nodes without geographical information has the ability to estimate their own locations with the help of known positions of anchor nodes which in turn helps in finding the locations of the one-hop normal nodes which is estimated from them. The second proposed scheme is that, it can estimate the moving direction of sensor nodes thereby increasing the accuracy level of localization. The quality of our scheme proposed is supported by the simulation results that the localization error in our proposed scheme is lower when compared to existing schemes in many of the mobility models and moving speeds.
CHAPTER 1: INTRODUCTION
Now a days, wireless sensor networks (WSNs) [1], [5] have been extensively used in a wide range of applications such as military operations, medical treatments, and the monitoring of the environment prevailing among the animals and their behavior in the forest. In many of the applications it was assumed that sensor nodes will have their positions known intact. For instance, the sensed data must go hand in hand with location information enabling the server to track the position of an expired event. Global Positioning System (GPS) equipment which is used to get the sensor's location is not cost effective expensive and it cannot be used indoors. Almost all applications require coarse localization accuracy, and that the cost effective solution is that anchor nodes (location aware nodes) of sensor network should come along with a GPS device, while the localization scheme helps the normal nodes (unaware of their location) get their positions automatically.
The localization schemes proposed earlier over this decade were designed for static sensor networks [11], [13], [14], [20], [26] most of which assume that sensors are nothing but mobile phones which know their own locations. In target tracking, the sensor nodes have been found to know their areas by tracking the locations of moving objects and that, the sensor nodes are found mobile in order to enlarge the sensing region, which explains the necessity of designing a localization scheme for mobile sensor networks. A Monte Carlo Localization (MCL) scheme specifically made for a mobile sensor network is proposed [12] in which, every sensor node is a mobile node. Every normal node collects the locations of its one-hop and two-hop anchor nodes by exchanging messages, and forms a new location set in almost all time slot.
The possible location set comprises various coordinates that help the normal node in locating others. The resulting possible locations are constrained by the communication range of anchor nodes and the region of location set in motion during the previous time slot, thereby handicapping the low anchor density in MCL, meaning the MCL fails to work well. By making use of the Monte Carlo method another range-free algorithm was designed and named as The Mobile and Static sensor network Localization (MSL) [19]. MSL uses the location estimation of all neighbors (not just anchor nodes) thereby improves the accuracy of location. The aforementioned designs and method are time-consuming since it is essential to keep sampling and filtering until enough samples are obtained to construct a new possible location set in every time slot. A bounding box (BB) method used to reduce the scope of searching the candidate samples is proposed in [22].
In this paper, we have a proposed a distributed localization approach to improve the localization error found in the previous methods. The proposed designed based on the Monte Carlo method. In this method, the possible locations of a normal node are constrained both from anchor nodes and from its one-hop normal nodes with calculated locations from the anchor nodes. Simulation results enables us to understand that the performance of my proposed scheme is better when compared to all of those previous schemes based on the fact that each normal node predicts its moving direction to drop some positions which can be neglected as impossible positions from the possible location set.
CHAPTER 2: ROUTING PROTOCOLS IN AD HOC NETWORK
PROTOCOLS
Table-Driven (or Proactive)
The nodes periodically exchange messages through a tabled list of routes to each destination in the network maintained by them. Initial delays before sending data are relatively very small as the routes to all destinations are always ready to use. There is a major demerit in this system when considering the bandwidth usage and network resources usage due to the routes that takes us to all destinations are always updated, even when they are not in use.
On-Demand (or Reactive)
This protocol is designed to overpower the demerit of the all time updated routes of the previous system. The major advantage in this system is that only when its necessary there happens the acquisition of the routing information. The overhead of maintaining unused routes is saved by calculating the needed routes on demand at each node, while on the other hand there will be a visible positive difference in the latency for sending data packets.
PROACTIVE:
DSDV (Destination-Sequence Distance Vector)
Every entry in the DSDV routing table will have : an address to the end point, number of hops leading to the destination, the following hop address thereby comprising all the destinations that a node can communicate with. While there is a communication happening between the source(A) and the destination(B), it checks the routing table for the entry that contains destination address as B which takes the hop address C for it.
The packets are sent from the source (A) to C which is then forwarded by it to B. C and the other intermediate nodes works in the same way until the packet reaches B. DSDV distinguishes the old from new by assigning a number to each entry in a sequential manner thereby prevents the loops thereof.
Routing information from DSDV are transferred using packets of two types namely full dump and incremental packet. The former is used to exchange the complete information each DSDV holds when they meet for the first time. From then on, they reduce the packet size by making use of the incremental packets to make notice of the changes made in the routing table. All the nodes in DSDV alters the routing information with time to time if new routes are found. For instance, if two routes are discovered, the one with larger sequence number or smaller hop count to destination in case of similar sequence numbered routes will be selected. DSDV has advantages of simple routing table format, simple routing operation and guarantee loop-freedom with the disadvantages being (i) overhead caused by periodical update (ii) waste of resource for finding all possible routes between each pair.
Advantages of DSDV:
simple routing table format.
simple routing operation and guarantee loop-freedom
Disadvantages of DSDV:
overhead caused by periodical update
resource wastage in finding routes as many as possible among each pair where only one route is used.
REACTIVE:
On-demand Routing Protocols
Routing information in on-demand trend is only created for destinations that are requested and Links are also monitored using periodical Hello messages. The source rediscovers the path in case of broken link in the path. Though on-demand strategy usually causes low overhead and are easily scalable, there will be more delay since the path is not ready always.
The following part talks about the AODV, DSR, TORA and ABR as characteristic protocols of on-demand trend.
AODV Routing
AODV stands for Ad hoc on demand distance vector routing (AODV) - a combination of DSDV and DSR. In AODV,
Each node maintains a routing table containing:
Active neighbor list: a list of neighboring nodes which makes active usage of this route entry. An immediate intimation is given to the neighbor node as and when the link is broken.
Destination address
Next-hop address in the way to the destination
Number of hops leading to the destination
Sequence number: for choosing route and prevent loop
Lifetime: time when that entry expires
There are two phases in AODV routing: Route Discovery and Route Maintenance. The routing table is referred, as and when there is a requirement to communicate with a destination. If the destination is seen, node sends the data in the similar way as in DSDV; else it begins the Route Discovery mechanism: Source node relays the Route Request packet to its neighbor nodes, which again rebroadcasts the broadcasted request to their neighbor nodes until a possible way to the destination is found. When RREQ is received by the intermediate node, the route to previous node is updated by the intermediate node and checks for: (i) a found entry which has a same destination with RREQ (ii) its sequence number is higher or equal to the same of RREQ. Else, it starts rebroadcasting RREQ. If found true, a RREP message is again sent to the source node and if RREP is routed back, the respective routing table is updated with the added next hop information by the node in the reverse path. If there is a receipt of similar RREQ as received before (checked by the sequence number) by the node, it leaves out the RREQ for preventing loop. If multiple RREP are received by the source node, one with greater sequence number is always selected. If multiple RREPs bear the same sequence number, the one with lower sum of hops to destination is chosen. Route Maintenance mechanism functions as the maintenance system of the route if found: Hello packets are sent periodically by each node to its neighbors to prove the availability. If a Hello packet is not received from a node in an interval, it is understood that link to particular node is broken. When a node does not receive any Hello messages, it will then nullify all of its related routes to the failed node and informs other neighbor using this node by Route Error packet. Route Discovery will have to be restarted if the source still needs to transmit the data to the destination in order to select a new path. AODV has many advantages and they are reducing the overhead control messages, low processing, quick adaptation to network topology change, highly scalable up to 10000 mobile nodes. Yet, there are disadvantages that AODV accepts only bi-directional links and there is noticeable time delay if a route has to be started, which in turn repairs the broken link.
DYNAMIC SOURCE ROUTING PROTOCOL
DSR is a reactive routing protocol which has the capability of managing a MANET without the help of periodic table update messages unlike other table-driven routing protocols. The special and specific design of DSR is highly useful and desirable in multi-hop wireless ad hoc networks. The network is made self-organized and self-configured with the help of Ad-hoc protocol, which is done by avoiding the necessity for an already existing network administration or infrastructure.
The procedure to find a path is carried only when there is a necessity for it thereby restricting the bandwidth following the On-Demand Routing. Here, the sender is called as the source initiator and the path from the source to the destination node is called the source routing. The sender (source, initiator) determines the complete path from the source node to the destination node (Source Routing) and stores the address information of the intermediate nodes of the route within the packets.
In comparison, DSR is beacon-less than the other reactive routing protocols like ABR or SSA, which indicated that there are no hello-messages between the nodes to show or inform their presence to the other neighboring nodes.
DSR designed for MANETs have a negligible diameter somewhere between 5 and 10 hops which in turn constrains the nodes from moving at a higher speed, meaning they are forced to move in a moderate speed. The spine of DSR is Link-State-Algorithms that is each node is capable of storing the optimum way to the end destination. Also, if there happens an alteration in the network topology, this information is spread to the whole network by flooding.
DSR contains 2 phases
Route Discovery (finding a path)
Route Maintenance (maintaining a path)
Route Discovery
If there is a route from node A route cache to the destination E, this route is immediately used. Else the Route Discovery protocol is started:
The initiator, Node floods the network for a Route Request by sending Route Request packets.
If the same request is received before from the same target or is the address is already listed in the Route Record the node B discards the request.
A Route Reply is sent to the initiator if node B is found to be the target of the Route Discovery. The Route Reply will contain the information of the optimum path stating from the initiator leading to the target. if this Route Reply is received by the initiator, it stores this concerned route in its Route Cache to be used later while sending subsequent packets to this destination.
If node B is found not to be the actual target, it then send this Route Request to all of its neighboring nodes (with exception to the initiator).
Path-finding-process: Route Request & Route Reply
Route Maintenance
In DSR every node functions in a perfect manner by confirming the receipt of packets by all the nearest hops in the Source Route and that each and every packet is sent just once by a node (hop-by-hop routing). If a node cannot receive a packet, it is then resent up taking maximum attempts until receipt of confirmation from the following hop in the sequence, meaning the next hop.
A Route Error message is sent to the initiator if there is a failure in the retransmission. The Source Route then removes the same from its Route Cache. Therefore, the initiator will have the ability to check its Route Cache if there are any another possible route leading to the target. If the cache does not have any route of that sort, a Route Request is then broadcasted
if node D doesn't acknowledge, the node C will return a Route Error to the initiator A but after many number of requests.
the broken-link-route in the cache is deleted immediately after the receipt of the Route Error message. If A has some other route to E, the packets are sent immediately using the new route.
Otherwise. If everything is a failure, then the initiator A restarts the Route Discovery process.
Advantages
Unlike other table-driven routing protocols the Reactive routing protocols does not have the necessity to occupy the network periodically to alter the routing table values. Control overhead is reduced by the efficient use of information in the Route cache by the intermediate nodes. The initiator finds the route only when there are no known route in the cache, which results in zero hello messages, which saves noticeable current and bandwidth.
Disadvantages
A broken link is communicated only to the initiator, therefore the Route Maintenance protocol does not locally repair them. The major demerit of DSR protocol is that it is efficient in MANETs with less than 200 nodes. Collusions are created between the packets by the flooding of network; hence there is a condition for the nodes to move in a moderate speed. Another drawback is that, always there will be a small time delay at the beginning of every new connection as the initiator spends time finding the route to the target, which then paves the way for the rest.
2.2.3. TORA (Temporary Ordered Routing Algorithm)
TORA is based on the link reversal algorithm and that each node in TORA constructs and holds along a table carrying the distance and status values of all of the available links. Detail information can be seen at [38]. TORA has three routing mechanisms:
Route Creation: TORA uses the concept of "height'' to discover multiple routes to a destination. TORA network follows a downstream Communication that is from higher to lower node. When there is no route to destination, source node starts Route Creation by broadcasting the Query messages (QRY). QRY is continually broadcasted until it reaches the destination or intermediate node that has the route to the destination. A Update (UPD) message containing the height information will be broadcasted by the reached node. a larger height for itself than the height in UPD will be set the node that receives this UPD, and then broadcasts the same. This is called reversal algorithm and is found to create number of direct links from the originator to the destination.
Route Maintenance: If there is a broken link and it is discovered, nodes make a new reference height and broadcast it to their neighbors. Thereby all the nodes in the link will change their reference height and Route Creation is done to reflect the change.
Route Erasure: The invalid routes are erased by flooding the "clear packet" through the network.
The advantages of TORA are: The multiple paths to destination decreases the creation of route in link broken case therefore decreases the overhead and the time delay to the network. TORA is also found to be very effective on large and mildly congested network [9].
The drawbacks include, requiring node synchronization due to "height" metric and potential for oscillation. Besides that, TORA may not guarantee to find all the routes for reservation in some cases.
CHAPTER 3
HARDWARE AND SOFTWARE SPECIFICATION
HARDWARE SPECIFICATION
This system was developed with IBM compatible personal computer with Pentium IV processor.
Main processor : Pentium IV processor 1.13 GHz
Hard disk capacity : 40GB
Cache memory : 512 MB
Monitor : LG Digital Color Monitor
Keyboard : Samsung
Mouse : Logitech
SOFTWARE SPECIFICATION
Operating system : Fedora 8 (linux)
Scripting language : Network Simulator 2.33
Protocol developed : C++
Scripting : Tool Command Language
SOFTWARE DESCRIPTION
5.3.1 THE NETWORK SIMULATOR 2.33 (NS2)
Network Simulator (NS2) is a part of the VINT project and a discrete event driven simulator developed at UC Berkeley. NS2 is developed as a collaborative environment and the major goal of NS2 is to support networking research and education. It is distributed freely and as open source in a large amount of institutes and people in development and research use, maintains and develops NS2. It is suitable for designing new protocols, comparing different protocols and traffic evaluations. Various versions are available for FreeBSD, Linux, Solaris, Windows and Mac OS X.
5.3.2 STRUCTURE OF NS2
NS2 is built using object oriented methods in C++ and OTcl (object oriented variant of Tcl.
Fig 5.1 Simplified User's View of Ns
As shown in Fig 5.1, the simulation scripts written in OTcl are interpreted by NS2. Various components such as event scheduler objects, network components libraries and setup module libraries are set up in the simulation environment. The user has written his simulation as OTcl script, plumbs the network components together to the complete simulation. If there is a need for new network components, it is free to implement them and to set them up in the viewer's simulation as well. The other major component besides network components is the event scheduler. It triggers the events of the simulation like sends packets, starts and stops tracing. Few parts of NS2 are written in C++ for the reason of efficiency. The control path (written in OTcl) is separated from The data path (written in C++). The compiled Data path object is then made available to the OTcl interpreter through an OTcl linkage (tclcl) which maps methods and member variables of the C++ object to methods and variables of the linked OTcl object. OTcl objects controls the C++ objects. Hence it has been made possible to add methods and member variables to a C++ linked OTcl object.
5.3.3 FUNCTIONALITIES OF NS2.33
NS2 has made available the functionalities for wired, wireless networks, tracing, and visualization.
• The wired world supportable include
- Routing DV, LS, and PIM-SM.
- Transport protocols: TCP and UDP for unicast and SRM for multicast.
- Traffic sources: web, ftp, telnet, cbr (constant bit rate), stochastic, real audio.
- Different types of Queues: drop-tail, RED, FQ, SFQ, DRR.
- Quality of Service: Integrated Services and Differentiated Services.
- Emulation.
• The wireless world supportable include
- Ad hoc routing with different protocols, e.g. AODV, DSR, DSDV, TORA
- Wired-cum-wireless networks
- Mobile IP
- Directed diffusion
- Satellite
- Senso-MAC
- Multiple propagation models (Free space, two-ray ground, shadowing)
- Energy models
• Tracing
• Visualization
- Network Animator (NAM)
- Trace Graph
• Utilities
- Mobile Movement Generator
Fig 5.2 OTcl and C++: the duality
5.3.3.1 MOBILE NETWORKING IN NS2.33
This section is about the wireless model. It was originally ported as CMU's Monarch group's mobility extension to NS2. The first section deals with the original mobility model ported from CMU/Monarch group. This section covers the internals of a mobile node, routing mechanisms and network components that are used to construct the network stack for a mobile node. Channel, Network interface, Radio propagation model, MAC protocols, Interface Queue, Link layer and Address resolution protocol model (ARP) are the components that are covered here. This section also covers CMU trace support and Generation of node movement and traffic scenario files. Pure wireless LANs or multihop ad-hoc networks are simulated by the original CMU model. Combined simulations of wired and wireless networks are also made possible by making few more extensions which has made the MobileIP to be extended to the wireless model.
5.3.3.2 THE BASIC WIRELESS MODEL IN NS
The MobileNode is at the core of the wireless model. It has additional supporting features too that allows simulations of multi-hop ad-hoc networks, wireless LANs and more. The object of the MobileNode is a split one. From the parent node, the C++ class MobileNode is derived and thus, it is the basic Node object with additional functionalities of a wireless and mobile node like ability to move within a given topology, ability to receive and transmit signals to and from a wireless channel etc. A vital variation between them, is that a MobileNode is not connected by means of Links to other nodes or mobilenodes. The internals of MobileNode, its routing mechanisms, the routing protocols dsdv, aodv, tora and dsr, creation of network stack allowing channel access in MobileNode, description of each stack component, trace support and movement/traffic scenario generation for wireless simulations are the few that are briefly described in this section.
5.3.3.3 MOBILE NODE: CREATING WIRELESS TOPOLOGY
MobileNode is the basic nsNode object with added functionalities. The additional functionalities include movement, ability to transmit and receive on a channel that allows it to be used to create mobile, wireless simulation environments. The MobileNode is a split object that is derived from the base class Node and the mobility features involve node movement, periodic position updates, maintaining topology boundary are implemented in C++ while plumbing of network components within MobileNode (as like classifiers, dmux , LL, Mac, Channel etc) have been implemented in Otcl.
Table 5.1: Available Options for Node Configuration
Option
Available Values
Default
General
Address type
Flat, Hierarchical
Flat
MPLS
ON,OFF
OFF
Both Satellite and Wireless Oriented
Wired Routing
ON,OFF
OFF
II Type
LL,LL/sat
OFF
Mac Type
Mac/802_11,Mac/Csma/Ca, Mac/Sat/Unslotted/Aloha,Mac/Tdma
OFF
ifq Type
Queue/DropTail, Queue/Droptail/PriQueue
OFF
Phy Type
Phy/wirelessPhy,Physat
OFF
Option
Available Values
Default
Satellite Oriented
satNodeType
Polar,Geo,Terminal,Geo-repeater
OFF
downlinkBW
<bandwidth value, e.g "2MB">
OFF
Wireless Oriented
Adhoc Routing
DIFFUSION/RATE,DIFFUSION/PROB,
DSDV,FLOODING,OMNICAST,AODV,TORA
OFF
propType
Propagation/2RayGround,Propagation Shadowing
OFF
propInstance
Propagation/2RayGround,Propagation Shadowing
OFF
antType
Antenna/Omni Antenna
OFF
Channel
Channel/Wireless Channel,Channel/sat
OFF
topoInstance
<toplogy file>
OFF
MobileIP
ON,OFF
OFF
Energy model
Energy model
OFF
Initial Energy
<value in joules>
OFF
rxPower
<value in W>
OFF
txPower
<value in W>
OFF
Idle Power
<value in W>
OFF
AgentTrace
ON,OFF
OFF
routerTrace
ON,OFF
OFF
macTrace
ON,OFF
OFF
movementTrace
ON,OFF
OFF
Errproc
UniformErrorProc
OFF
FECProc
?
?
toraDebug
ON,OFF
OFF
