1.1 HISTORY OF ONLINE NAVIGATION SYSTEMS
It’s tough to believe, but in-car GPS navigation has already been around for more than a decade. Yet were it not for politics—and Einstein’s theory of relativity—we wouldn’t even have it in the first place.
Twenty years ago, a road trip meant a bunch of fold-out maps stuffed into your glove box or your car door panel pockets. Pulling over, unfolding one like a giant newspaper, and then figuring out where you were and how it corresponded to what you were seeing through the windshield was the norm. Along the way, those maps gave way to MapQuest or Yahoo Maps print-outs, and now, fortunately, we’ve got portable navigation devices (PNDs), in-dash GPS systems, and GPS-enabled smartphones. Voice-enabled navigation is more commonplace than ever, as the average PND price keeps getting lower and lower, and high-quality navigation apps are available for most smartphones. Android phones even come with free Google Maps with driving directions.
But to figure out how we got here, we need to first look at how it all began.
Einstein and the Origins of GPS
The U.S. Department of Defense first developed satellite-based global positioning technology for the military. An early satellite-based system dubbed TRANSIT was up and running as early as 1960, with more refined and precise versions involving multiple satellites in general military use by the early 1980s. But it wasn’t until 2000 that precision GPS navigation became open to the public.
Publicly available GPS devices had already been around since the early 1980s. But the military added interference to the signals to ensure their own version was the only one that could be used with any precision. After four years of deliberations, President Clinton signed a bill in 2000 ordering the military to cease scrambling satellite signals used by civilians. This instantly upgraded the accuracy of the few consumer-based systems already in existence by a factor of 10, and opened the doors to a much larger, consumer electronics-based industry for GPS navigation.
Today, a network of 24 U.S.-based GPS satellites orbit the earth, ensuring that at least three are available at any one time for a device’s position request anywhere on the globe. Russia’s own GLONASS system of 22 satellites will soon work with some compatible smartphones in the U.S. for additional accuracy.
Most people don’t realize that in order for global positioning to work, Einstein’s theories of special relativity and general relativity must come into play. On a basic level, GPS finds your position by looking at the time stamp from several satellites orbiting the earth, how far away each one is from you, and how far apart each one is from the other. With that data, the system triangulates your position on the ground. But because of relativity, the clocks in the satellites advance ever so slightly faster than clocks on the surface of the Earth. Plus, moving clocks are slower than ones standing still—again, by a very tiny amount.
While those two effects work against each other, the net result isn’t equal: You end up with a discrepancy of roughly 38 microseconds per day. That incredibly small difference is still enough to report your actual position off by miles, which would render the GPS system worthless, were it not for allowing for relativistic effects.
The Road to In-Car Navigation
Even after 2000, it would be a while before consumers would see GPS navigation in cars en masse. Fortunately, the dot com boom was already coming to the rescue. Beginning around the turn of the century, computer-generated, turn-by-turn directions from websites like MapQuest were a common sight. Not only were these websites godsends for finding unfamiliar hotels and restaurants, but they also assisted plenty of small businesses heavily reliant on driving—think of home improvement contractors, real estate agents, and freight services, just to name a few examples.
Map-based websites weren’t perfect, though. Early routing algorithms were imprecise, and sometimes repeated steps repeatedly—long lists of instructions that basically said to stay on the same road for 12 miles were a constant source of frustration. Plus, you still had to print them out and take them with you, which meant you needed to pull over to read the next few steps. And if you wandered off course, you were just as lost as you would have been with a map—worse if you left the actual map at home, since the printed directions were for one specific route.
1.2 NOISE POLLUTION-AN UNDERRATED PROBLEM
Noise pollution is a growing environmental problem. It’s far from just being an annoyance as it has very real negative effects on humans. But according to today’s scenario noise pollution is not gaining much concern due to ignorance about the serious effect of noise on public community. We are forgetting that noise can also be considered as an important pollutant of the environment causing various mental problems. In humans, it’s been shown that exposure to moderately high level of noise for a continuous amount of time can increase blood pressure and cause other cardiac issues-even if a person is not particularly disturbed.
According to Robert Koch, a Nobel Prize winner German Bacteriologist, “A day will come man will have to fight merciless noise as the worst enemy of health”. In India only, major cities like Mumbai, Delhi, Bangalore etc., are already fighting with this major problem of noise pollution. Delhi, for example, has recorded noise levels double that recommended by the WHO. The ‘wall of noise’ effect created by traffic, as well as explosive noise of firecrackers, used as part of religious practices, have been linked to child deafness. Law is difficult to prosecute due to the lack of instrumentation for measuring noise.
This task of monitoring noise can be performed with the help of sensors, which can be fitted in different areas. Our Project, Noise-Based Navigation System will also work according to the data collected by such sensors and will help in controlling noise pollution to some extent. According to many surveys conducted in past, traffic and related noise were the most experienced i.e. approximately 65% and such noises are the most bothersome noises which can cause major health issues. Some more data suggests car honking itself create 57% of the noise on Indian roads. Therefore, controlling the traffic based on noise intensity could be a good initiative towards controlling the problem of Noise Pollution.
1.3 OVERVIEW OF TECHNICAL AREA
1.3.1 INTRODUCTION TO C++
C++ is a general-purpose programming language. It has imperative, object-oriented and generic programming features, while also providing facilities for low-level memory manipulation.
It was designed with a bias toward system programming and embedded, resource-constrained and large systems, with performance, efficiency and flexibility of use as its design highlights. C++ has also been found useful in many other contexts, with key strengths being software infrastructure and resource-constrained applications, including desktop applications, servers (e.g. e-commerce, web search or SQL servers), and performance critical applications (e.g. telephone switches or space probes)
C++ is standardized by the International Organization for standardization (ISO), with the latest standard version ratified and published by ISO in December 2014 as ISO/IEC 14882:2014 (informally known as C++14). C++ was initially standardized in 1998 as ISO/IEC 14882:2003, standard. The current C++14 standard supersedes these and C++11, with new features and an enlarged standard library.
Throughout C++’s life, its development and evolution has been informally governed by a set of rules that its evolution should follow:
It must be driven by actual problems and its features should be useful immediately in real world programs.
Every feature should be implementable (with a reasonably obvious way to do so).
Programmers should be free to pick their own programming style, and that style should be fully supported by C++.
Allowing a useful feature is more important than preventing every possible misuse of C++.
It should provide facilities for organizing programs into well-defined separate parts and provide facilities for combining separately developed parts.
No implicit violations of the type system (but allow explicit violations; that is, those explicitly requested by the programmer).
User-created types need to have the same support and performance as built-in types.
Unused features should not negatively impact created executables (e.g. in lower performance).
There should be no language beneath C++ (except assembly language).
C++ should work alongside other existing programming languages, rather than fostering its own separate and incompatible programming environment.
If the programmer’s intent is unknown, allow the programmer to specify it by providing manual control.
1.3.2 OVERVIEW OF LINUX
Linux is a family of free and open-source software operating systems built around the Linux kernel. Typically, Linux is packaged in a form known as a Linux distribution (or distro for short) for both desktop and server use. The defining component of a Linux distribution is the Linux kernel an operating system kernel first released on September 17, 1991, by Linus Torvalds. Many Linux distributions use the word “Linux” in their name. The Free Software Foundation uses the name GNU/Linux to refer to the operating system family, as well as specific distributions, to emphasize that most Linux distributions are not just the Linux kernel, and that they have in common not only the kernel, but also numerous utilities and libraries, a large proportion of which are from the GNU project. This has led to some controversy.
Linux was originally developed for personal computers based on the Intel x86 architecture but has since been ported to more platforms than any other operating system. Because of the dominance of the Linux kernel-based Android OS on smartphones, Linux has the largest installed base of all general-purpose operating systems. Linux is also the leading operating system on servers and other big iron systems such as mainframe computers, and the only OS used on TOP500 supercomputers (since November 2017, having before gradually eliminated all competitors). It is used by around 2.3% of desktop computers. The Chromebook, which runs the Linux kernel-based Chrome OS, dominates the US K–12 education market and represents nearly 20% of the sub-$300 notebook sales in the US. Linux also runs on embedded systems—devices whose operating system is typically built into the firmware and is highly tailored to the system. This includes TiVo and similar DVR devices, network routers, facility automation controls, televisions, video game consoles and smartwatches. Many smartphones and tablet computers run Android and other Linux derivatives.
The development of Linux is one of the most prominent examples of free and open-source software collaboration. The underlying source code may be used, modified and distributed commercially or non-commercially—by anyone under the terms of its respective licenses, such as the GNU General Public License.
Some of the most popular and mainstream Linux distributions are Arch Linux, CentOS, Debian, Fedora, Gentoo Linux, Linux Mint, Mageia, openSUSE and Ubuntu, together with commercial distributions such as Red Hat Enterprise Linux and SUSE Linux Enterprise Server. Distributions include the Linux kernel, supporting utilities and libraries, many of which are provided by the GNU Project, and usually a large amount of application software to fulfil the distribution’s intended use. Desktop Linux distributions include a windowing system, such as X11, Mir or a Wayland implementation, and an accompanying desktop environment such as GNOME or KDE Plasma; some distributions may also include a less resource-intensive desktop, such as LXDE or Xfce. Distributions intended to run on servers may omit all graphical environments from the standard install, and instead include other software to set up and operate a solution stack such as LAMP. Because Linux is freely redistributable, anyone may create a distribution for any intended use.
Ubuntu is a computer operating system based on the Debian Linux distribution and distributed as free and open source software, using its own desktop environment. It features Unity, a reimagined way to use your computer. Unity is designed to minimize the distractions, give you more room to work, and help you get things done.
A default installation of Ubuntu contains a wide range of software that includes LibreOffice, Firefox, Thunderbird, Transmission, and several lightweight games such as Sudoku and chess. Many additional software packages are accessible from the built in Ubuntu Software Center as well as any other APT-based package management tools. Many additional software packages that are no longer installed by default, such as Evolution, GIMP, Pidgin, and Synaptic, are still accessible in the repositories, installable with the built in Ubuntu Software Center; or by any other APT-based package management tool. Cross-distribution snap packages and flatpaks are also available.
Ubuntu operates under the GNU General Public License (GPL) and all the application software installed by default is free software. In addition, Ubuntu installs some hardware drivers that are available only in binary format, but such packages are clearly marked in the restricted component.
In this project we are using Ubuntu 16.04 LTS, some snapshots for the same can be seen below in Fig 1.1 and Fig 1.2.
Fig 1.1 shows the Ubuntu desktop and the GNOME Terminal in which the commands are given can be seen in Fig 1.2. In a Linux system, the terminal is a command line interface that interprets a user’s command and script files and tells the server operating system what to do with them. When the user first login to the server, it is dropped into the command prompt, where he/she can issue required commands to the server.
Fig 1.1 Ubuntu Desktop
Fig 1.2 Ubuntu Terminal
It is much faster to complete some tasks using an Ubuntu Terminal than with graphical applications and menus. Another benefit is allowing access to many more commands and scripts.
A common terminal task of installing an application can be achieved within a single command, compared to navigating through the Software Centre or Synaptic Manager.
1.4 OVERVIEW OF THE REPORT
This report will comprise of all the phases taken during the development of this project starting from the “Synopsis” till “Evolution of the project”. This report starts with the survey and analysis of the problems faced currently due to constantly increasing noise pollution every day. It consists of the analysis of current scenario followed by problem definition and our proposed solution.
Next chapter consists of the Literature review, which appropriately signifies the problem of noise pollution and various steps taken by our government and other organizations to tackle this serious problem. In this chapter, different research papers are also discussed which shows some existing work in designing efficient navigation algorithms.
After the literature study, we have defined the problem statement on which we are working. A thorough study of the problem statement helped us to simplify our approach and come up with an efficient solution to handle this serious problem of increased noise. With proper definition of the problem statement and having a clear idea of our approach we started implementation part using appropriate tools and technologies described briefly inside in this report. Here we have mentioned all the problems that had arrived during implementation and have found the solution to these problems.
The next chapters included the conclusion, obtained after successful implementation and getting desired results. At last, all the references and sources are mentioned which were referred while writing this thesis report.
2.1 NOISE POLLUTION SURVEY
Noise is an urgent problem in India. Mumbai, for example, has recorded noise levels double that recommended by the WHO. The ‘wall of noise’ effect created by traffic, as well as explosive noise of firecrackers, used as part of religious practices, have been linked to child deafness. Law is difficult to prosecute due to the lack of instrumentation for measuring noise. Thus, there is an urgent need for effective noise monitoring.
According to “Indian Noise Pollution Research Report”, published in 2015 by John Halloran some findings are listed as:
The headlines are:
Traffic and associated noise was the most frequently experienced
Traffic and associated noise were rated the most bothersome
Health, loss of concentration and stress were the most commonly reported effects of traffic noise
There was not a direct correlation between type of noise and how bothersome it is; or between frequency and how bothersome it is
Different types of noise have different effects. Some prevent sleep, for example; others do not
91% of respondents wanted to contribute to reducing noise levels
70% said they would always send messages with recordings of noise where it was noticed, if they got free texts equivalent to or more than the cost of sending
< 50% would do be prepared to do extra work, i.e. annotating the noise recording
Detailed findings follow.
2- How frequently people experience different kinds of noise
Respondents were asked whether they hear types of noise ‘always’, ‘nearly’, or ‘never’. (The findings rank noise sources according to the always percentage, highest first)
Traffic 68% (rarely 27%; never 5%)
Honking horns 57% (rarely 33%; never 10%)
Heavy trucks, planes, trains 57% (rarely 36%; never 7%)
People on phone 55% (rarely 32%; never 13%)
Sound from music system 47% (rarely 32%; never 13%)
Construction site 37% (rarely 40%; never 13%)
Loudspeakers 34% (rarely 59%; never 7%)
Home appliances 26% (rarely 59%; never 15%)
Industry 19% (rarely 57%; never 24%)
People fighting in roads 18% (rarely 70%; never 12%)
Hawkers 18% (rarely 57%; never 25%)
Firecrackers 17% (rarely 68%; never 15%)
The majority noise problem is traffic of various types; the first three items in the list. Personal phone use was also ‘always’ experienced by over half the respondents.
3- How much different types of noise bother people
For noise respondents said they ‘always’ experience, we asked how much it bothered them: very much, not much, or not at all. (The items are ranked according to the ‘very much’ percentage, highest first, with the experience frequency rank above in brackets)
Traffic 50% (not much 44%; not at all 6%)
Heavy trucks, planes, trains 50% (not much 40%; not at all 10%)
Loudspeakers 49% (not much 39%; not at all 12%)
Honking horns 48% (not much 40%; not at all 12%)
Construction site 30% (not much 52%; not at all 18%)
People fighting in roads 29% (not much 54%; not at all 17%)
Sound from music system 29% (not much 53%; not at all 18%)
People on phone 28% (not much 50%; not at all 22%)
Firecrackers 27% (not much 51%; not at all 22%)
Hawkers 25% (not much 51%; not at all 24%)
Industry 24% (not much 54%; not at all 22%)
Home appliances 19% (not much 61%; not at all 20%)
It can be seen from this that the noise most commonly experienced by respondents,
traffic (and associated), is also the most bothersome. However, the intrusiveness of noise does not always correlate with its frequency. Loudspeakers, for example, are bothersome even though relatively infrequent; whilst people on phone is not very intrusive despite being frequently experienced.
4- Why noise bothers people: severity of effects
When asked why the noise bothered respondents. There are patterned responses. For traffic; heavy trucks, planes and trains; honking horns; construction and industry, health, loss of concentration, and stress / annoyance are the most important three factors, each accounting for approximately a fifth to two fifths of responses. The other two factors, loss of sleep and ‘other’, are less important, each accounting for around 10% of the responses. This suggests that impersonal, non-musical ambient noise has several effects, none standing out, but sleep deprivation is not a major issue.
Loudspeakers, people on phone and sounds from music system all have a bigger, standout effect from loss of concentration which is the majority response of about 45 – 50%; there is also a higher loss of sleep effect of about 25%. This suggests that musical and personal noise is associated with more sleep deprivation. Health issues is a big factor for firecrackers; stress for fighting.
These findings suggest that noise needs to be considered not just in terms of frequency but also how bothersome it is and in terms of its effects. This implies that there needs to be some way of assessing severity both in terms of how far people notice noise and what its effects are where there may be different levels of severity.
5- Willingness to engage in participatory sensing
91% of respondents wanted to contribute to reducing noise levels. 98% have phones. 70% said they would always send messages with recordings of noise where it was noticed. The conditions under which the majority would do so are if they got free texts equivalent to or more than the cost of sending. Only a minority agreed to do additional work to describe content either by voice or text. This suggests that if incentivized noise recordings could be elicited from around 70% of respondents where this is a matter of sending a recording without further work.
Based on the observations, after studying this this complete report, we came up with a solution to design such a navigation system that can control the traffic based on noise intensity of any area. To achieve the goal, the very first requirement was to design a shortest path algorithm for traffic navigation with noise intensity as main factor controlling that traffic. Before starting the work in this direction, number of research works were referred which are summarized in next section 2.2
2.2PREVIOUS WORK ON NAVIGATION ALGORITHMS
PROBLEM DEFINITION AND PROPOSED SOLUTION
3.1 PROBLEM STATEMENT
Noise pollution is a growing environmental issue affecting both health and behavior. Unwanted sound (noise) can damage psychological and physiological health. Noise pollution can cause hypertension, high stress levels, tinnitus, hearing loss, sleep disturbances, and other harmful effects.
Execution of effective law is one solution but lack of instrumentation in measuring noise is the major issue. An alternative solution to monitor noise can be to make use of sensors collecting data from various areas. Noise-intensity can be used as a driving factor for noise measurement.
Therefore, controlling the traffic based on noise intensity could be a good initiative towards controlling the problem of Noise Pollution.
3.2 OUR SOLUTION
TOOLS AND TECHNOLOGIES
4.1 INTRODUCTION TO NETWORK SIMULATOR
NS (from network simulator) is a name for a series of discrete event network simulators, specifically NS-1, and NS-2. All of them are discrete-event computer network simulators, primarily used in research and teaching.
NS is built using C++ and Python with scripting capability. The ns library is wrapped by Python thanks to the pybindgen library which delegates the parsing of the ns C++ headers to gccxml and pygccxml to automatically generate the corresponding C++ binding glue. These automatically-generated C++ files are finally compiled into the ns Python module to allow users to interact with the C++ ns models and core through Python scripts. The ns simulator features an integrated attribute-based system to manage default and per-instance values for simulation parameters.
A short description along with the history of development of the two versions, released till date, is given below:
The first version of NS, known as NS-1, was developed at Lawrence Berkeley National Laboratory (LBNL) in the 1995-97 timeframe by Steve McCanne, Sally Floyd, Kevin Fall, and other contributors. This was known as the LBNL Network Simulator and derived in 1989 from an earlier simulator known as REAL by S. Keshav.
NS-2 began as a revision of NS-1. In 1995 ns development was supported by DARPA through the VINT project at LBL, Xerox PARC, UCB, and USC/ISI. In 2000, NS-2 development was support through DARPA with SAMAN and through NSF with CONSER, both at USC/ISI, in collaboration with other researchers including ACIRI. NS-2 incorporates substantial contributions from third parties, including wireless code from the UCB Daedelus and CMU Monarch projects and Sun Microsystems.
4.2 NS2 SCENARIO GENRATOR
NS2 Scenarios Generator (NSG) is a tcl script generator tool used to generate TCL Scripts automatically.
NSG is a Java based tool that runs on any platform and can generate TCL Scripts for Wired as well as Wireless Scenarios for Network Simulator – 2. The procedure to execute these TCL Scripts on NS-2 is same as those of manually written TCL Scripts. Some of the main features of NS2 Scenarios Generator (NSG) are as mentioned below:
Creating Simplex and Duplex links for Wired network.
Creating Wired and Wireless nodes just by drag and drop.
Creating Grid, Random and Chain topologies.
Creating TCP and UDP agents. Also supports TCP Tahoe, TCP Reno, TCP New-Reno and TCP Vegas.
Supports Ad Hoc routing protocols such as DSDV, AODV, DSR and TORA.
Supports FTP and CBR applications.
Supports node mobility.
Setting the packet size, start time of simulation, end time of simulation, transmission range and interference range in case of wireless networks, etc.
Setting other network parameters such as bandwidth, etc., for wireless scenarios. Some snapshots of the NSG can be seen in the figures below:
Fig 4.1 Wired Scenario using NSG
Fig 4.2 Automatic tcl file generated according to the scenario.
Fig 4.3 Wireless Scenario using NSG
Fig 4.4 Describing parameters for wireless scenario
In the above snapshots, Fig 4.1 and Fig 4.3 shows the wired and wireless scenarios generated using NSG. The tcl file is automatically generated and thus can be directly used to obtain desired results.
Fig 4.2 represents the tcl file which is generated according to the scenario created by the user. In this case the circular dots represent the nodes and the edges represents the path between the nodes.
Fig 4.4 shows the wireless scenario in which user is required to set the parameters for the node initialization and the algorithm to be used for transfer of data packets.
4.3 ROUTING PROTOCOLS DEFINED IN NS-2
In NS-2, we can design our network based on two scenarios i.e. wired network and wireless network. Thus, different routing protocols are defined for each scenario for example, DVR protocol, Link State routing protocol for wired and AODV, DSDV for wireless networks.
More precise description of these predefined protocols can be seen in next section 4.3.
4.3.1 PROTOCOLS FOR WIRED NETWORK
188.8.131.52 DISTANCE VECTOR ROUTING PROTOCOL (DVR)
Distance vector routing is a simple distributed routing protocol. Distance vector routing allows routers to automatically discover the destinations reachable inside the network as well as the shortest path to reach each of these destinations. The shortest path is computed based on metrics or costs that are associated to each link.
The term distance vector refers to the fact that the protocol manipulates vectors (arrays) of distances to other nodes in the network. The distance vector algorithm was the original ARPANET routing algorithm and was implemented more widely in local area networks with the Routing Information Protocol (RIP).
Distance-vector routing protocols measure the distance by the number of routers a packet must pass, one router counts as one hop. Some distance-vector protocols also consider network latency and other factors that influence traffic on a given route. To determine the best route across a network router on which a distance-vector protocol is implemented exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols also require that a router informs its neighbors of network topology changes periodically.
Distance-vector routing protocols use the Bellman–Ford algorithm and Ford– Fulkerson algorithm to calculate the best route. Another way of calculating the best route across a network is based on link cost and is implemented through link-state routing protocols.
184.108.40.206 LINK STATE ROUTING PROTOCOL
Link state routing is the second family of routing protocols. While distance vector routers use a distributed algorithm to compute their routing tables, link-state routers exchange messages to allow each router to learn the entire network topology. Based on this learned topology, each router is then able to compute its routing table by using a shortest path computation
For link-state routing, a network is modelled as a directed weighted graph. Each router is a node, and the links between routers are the edges in the graph. A positive weight is associated to each directed edge and routers use the shortest path to reach each destination. In practice, different types of weight can be associated to each directed edge.
LSR is one of the two main classes of routing protocols used in packet switching networks for computer communications, the other being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and intermediate system to intermediate system (IS-IS).
The link-state protocol is performed by every switching node in the network (i.e., nodes that are prepared to forward packets; in the Internet, these are called routers). The basic concept of link-state routing is that every node constructs a map of the connectivity to the network, in the form of a graph, showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical path from it to every possible destination in the network. Each collection of best paths will then form each node’s routing table.
This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors. In a link-state protocol the only information passed between nodes is connectivity related. Link-state algorithms are sometimes characterized informally as each router, “telling the world about its neighbors.”
4.3.2 PROTOCOLS FOR WIRELESS NETWORK
220.127.116.11 DESTINATION SEQUENCED DISTANCE VECTOR ROUTING PROTOCOL (DSDV)
The Destination-Sequenced Distance-Vector (DSDV) Routing Algorithm is based on the idea of the classical Bellman-Ford Routing Algorithm with certain improvements.
Every mobile station maintains a routing table that lists all available destinations, the number of hops to reach the destination and the sequence number assigned by the destination node. The sequence number is used to distinguish stale routes from new ones and thus avoid the formation of loops. The stations periodically transmit their routing tables to their immediate neighbors. A station also transmits its routing table if a significant change has occurred in its table from the last update sent. So, the update is both time-driven and event-driven. The routing table updates can be sent in two ways: – a “full dump” or an incremental update. A full dump sends the full routing table to the neighbors and could span many packets whereas in an incremental update only those entries from the routing table are sent that has a metric change since the last update and it must fit in a packet. If there is space in the incremental update packet, then those entries may be included whose sequence number has changed. When the network is relatively stable, incremental updates are sent to avoid extra traffic and full dump are relatively infrequent. In a fast-changing network, incremental packets can grow big so full dumps will be more frequent. Each route update packet, in addition to the routing table information, also contains a unique sequence number assigned by the transmitter. The route labeled with the highest (i.e. most recent) sequence number is used. If two routes have the same sequence number, then the route with the best metric (i.e. shortest route) is used. Based on the history, the stations estimate the settling time of routes. The stations delay the transmission of a routing update by settling time so as to eliminate those updates that would occur if a better route were found very soon.
18.104.22.168 WIRELESS ROUTING PROTOCOL (WRP)
The Wireless Routing Protocol (WRP) is a table-based distance-vector routing protocol. Each node in the network maintains a Distance table, a Routing table, a Link-Cost table and a Message Retransmission list.
The Distance table of a node x contains the distance of each destination node y via each neighbor z of x. It also contains the downstream neighbor of z through which this path is realized. The Routing table of node x contains the distance of each destination node y from node x, the predecessor and the successor of node x on this path. It also contains a tag to identify if the entry is a simple path, a loop or invalid. Storing predecessor and successor in the table is beneficial in detecting loops and avoiding counting-to-infinity problems. The Link-Cost table contains cost of link to each neighbor of the node and the number of timeouts since an error-free message was received from that neighbor. The Message Retransmission list (MRL) contains information to let a node know which of its neighbor has not acknowledged its update message and to re transmit update message to that neighbor.
Node exchange routing tables with their neighbors using update messages periodically as well as on link changes. The nodes present on the response list of update message (formed using MRL) are required to acknowledge the receipt of update message. If there is no change in routing table since last update, the node is required to send an idle Hello message to ensure connectivity. On receiving an update message, the node modifies its distance table and looks for better paths using new information. Any new path so found is relayed back to the original nodes so that they can update their tables. The node also updates its routing table if the new path is better than the existing path. On receiving an ACK, the mode updates its MRL. A unique feature of this algorithm is that it checks the consistency of all its neighbors every time it detects a change in link of any of its neighbors. Consistency check in this manner helps eliminate looping situations in a better way and has fast convergence.
22.214.171.124 GLOBAL STATE ROUTING PROTOCOL (GSR)
Global State Routing (GSR) is like DSDV. It takes the idea of link state routing but improves it by avoiding flooding of routing messages.
In this algorithm, each node maintains a Neighbor list, a Topology table, a Next Hop table and a Distance table. Neighbor list of a node contains the list of its neighbors (here all nodes that can be heard by a node are assumed to be its neighbors.). For each destination node, the Topology table contains the link state information as reported by the destination and the timestamp of the information. For each destination, the Next Hop table contains the next hop to which the packets for this destination must be forwarded. The Distance table contains the shortest distance to each destination node.
The routing messages are generated on a link change as in link state protocols. On receiving a routing message, the node updates its Topology table if the sequence number of the message is newer than the sequence number stored in the table. After this the node reconstructs its routing table and broadcasts the information to its neighbors.
126.96.36.199 FISHEYE STATE ROUTING PROTOCOL (FSR)
Fisheye State Routing (FSR) is an improvement of GSR. The large size of update messages in GSR wastes a considerable amount of network bandwidth. In FSR, each update message does not contain information about all nodes. Instead, it exchanges information about closer nodes more frequently than it does about farther nodes thus reducing the update message size. So, each node gets accurate information about neighbors and the detail and accuracy of information decreases as the distance from node increases. The scope is defined in terms of the nodes that can be reached in a certain number of hops. The center node has most accurate information about all nodes in the white circle and so on. Even though a node does not have accurate information about distant nodes, the packets are routed correctly because the route information becomes more and more accurate as the packet moves closer to the destination. FSR scales well to large networks as the overhead is controlled in this scheme.
188.8.131.52 HIERARCHICAL STATE ROUTING (HSR)
The characteristic feature of Hierarchical State Routing (HSR) is multilevel clustering and logical partitioning of mobile nodes. The network is partitioned into clusters and a cluster-head elected as in a cluster-based algorithm. In HSR, the cluster-heads again organize themselves into clusters and so on. The nodes of a physical cluster broadcast their link information to each other. The cluster-head summarizes its cluster’s information and sends it to neighbor cluster-heads via gateway. A node at each level floods to its lower level the information that it obtains after the algorithm has run at that level. So, the lower level has a hierarchical topology information. Each node has a hierarchical address. A gateway can be reached from the root via more than one path, so gateway can have more than one hierarchical address. A hierarchical address is enough to ensure delivery from anywhere in the network to the host.
In addition, nodes are also partitioned into logical subnetworks and each node is assigned a logical address <subnet, host>. Each subnetwork has a location management server (LMS). All the nodes of that subnet register their logical address with the LMS. The LMS advertise their hierarchical address to the top levels and the information is sent down to all LMS too. The transport layer sends a packet to the network layer with the logical address of the destination. The network layer finds the hierarchical address of the hierarchical address of the destination’s LMS from its LMS and then sends the packet to it. The destination’s LMS forwards the packet to the destination. Once the source and destination know each other’s hierarchical addresses, they can bypass the LMS and communicate directly. Since logical address/hierarchical address is used for routing, it is adaptable to network changes.
184.108.40.206 ZONE BASED HIERARCHICAL LINK STATE ROUTING PROTOCOL (ZHLS)
In Zone-based Hierarchical Link State Routing Protocol (ZHLS), the network is divided into non-overlapping zones. Unlike other hierarchical protocols, there is no zone-head. ZHLS defines two levels of topologies – node level and zone level. A node level topology tells how nodes of a zone are connected to each other physically. A virtual link between two zones exists if at least one node of a zone is physically connected to some node of the other zone. Zone level topology tells how zones are connected. There are two types of Link State Packets (LSP) as well – node LSP and zone LSP. A node LSP of a node contains its neighbor node information and is propagated with the zone where as a zone LSP contains the zone information and is propagated globally. So, each node has full node connectivity knowledge about the nodes in its zone and only zone connectivity information about other zones in the network. So, given the zone id and the node id of a destination, the packet is routed based on the zone id till it reaches the correct zone. Then in that zone, it is routed based on node id. A ;zone id, node [email protected]; of the destination is sufficient for routing so it is adaptable to changing topologies.
ON-DEMAND ROUTING PROTOCOLS
These protocols take a lazy approach to routing. In contrast to table-driven routing protocols all up-to-date routes are not maintained at every node, instead the routes are created as and when required. When a source wants to send to a destination, it invokes the route discovery mechanisms to find the path to the destination. The route remains valid till the destination is reachable or until the route is no longer needed.
220.127.116.11 AD HOC ON-DEMAND DISTANCE VECTOR ROUTING (AODV)
Ad hoc On-demand Distance Vector Routing (AODV) is an improvement on the DSDV algorithm discussed in section 2.1. AODV minimizes the number of broadcasts by creating routes on-demand as opposed to DSDV that maintains the list of all the routes.
To find a path to the destination, the source broadcasts a route request packet. The neighbors in turn broadcast the packet to their neighbors till it reaches an intermediate node that has a recent route information about the destination or till it reaches the destination. A node discards a route request packet that it has already seen. The route request packet uses sequence numbers to ensure that the routes are loop free and to make sure that if the intermediate nodes reply to route requests, they reply with the latest information only.
When a node forwards a route request packet to its neighbors, it also records in its tables the node from which the first copy of the request came. This information is used to construct the reverse path for the route reply packet. AODV uses only symmetric links because the route reply packet follows the reverse path of route request packet. As the route reply packet traverses back to the source, the nodes along the path enter the forward route into their tables.
If the source moves, then it can reinitiate route discovery to the destination. If one of the intermediate nodes move, then the moved nodes neighbor realizes the link failure and sends a link failure notification to its upstream neighbors and so on till it reaches the source upon which the source can reinitiate route discovery if needed.
18.104.22.168 DYNAMIC SOURCE ROUTING PROTOCOL (DSR)
The Dynamic Source Routing Protocol is a source-routed on-demand routing protocol. A node maintains route caches containing the source routes that it is aware of. The node updates entries in the route cache as and when it learns about new routes.
The two major phases of the protocol are: route discovery and route maintenance. When the source node wants to send a packet to a destination, it looks up its route cache to determine if it already contains a route to the destination. If it finds that an unexpired route to the destination exists, then it uses this route to send the packet. But if the node does not have such a route, then it initiates the route discovery process by broadcasting a route request packet. The route request packet contains the address of the source and the destination, and a unique identification number. Each intermediate node checks whether it knows of a route to the destination. If it does not, it appends its address to the route record of the packet and forwards the packet to its neighbors. To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and it’s address is not present in the route record of the packet.
A route reply is generated when either the destination or an intermediate node with current information about the destination receives the route request packet. A route request packet reaching such a node already contains, in its route record, the sequence of hops taken from the source to this node. If the route reply is generated by the destination, then it places the route record from route request packet into the route reply packet. On the other hand, if the node generating the route reply is an intermediate node then it appends its cached route to destination to the route record of route request packet and puts that into the route reply packet.
To send the route reply packet, the responding node must have a route to the source. If it has a route to the source in its route cache, it can use that route. The reverse of route record can be used if symmetric links are supported. In case symmetric links are not supported, the node can initiate route discovery to source and piggyback the route reply on this new route request.
DSRP uses two types of packets for route maintenance: – Route Error packet and Acknowledgements. When a node encounters a fatal transmission problem at its data link layer, it generates a Route Error packet. When a node receives a route error packet, it removes the hop in error from its route cache. All routes that contain the hop in error are truncated at that point. Acknowledgment packets are used to verify the correct operation of the route links.
22.214.171.124 TEMPORALLY ORDERED ROUTING ALGORITHM (TORA)
The Temporally Ordered Routing Algorithm (TORA) is a highly adaptive, efficient and scalable distributed routing algorithm based on the concept of link reversal. TORA is proposed for highly dynamic mobile, multihop wireless networks. It is a source-initiated on-demand routing protocol. It finds multiple routes from a source node to a destination node. The main feature of this protocol is that the control messages are localized to a very small set of nodes near the occurrence of a topological change. To achieve this, the nodes maintain routing information about adjacent nodes. The protocol has three basic functions: Route creation, Route maintenance, and Route erasure. Each node has a quintuple associated with it
Logical time of a link failure
The unique ID of the node that defined the new reference level
A reflection indicator bit
A propagation ordering parameter
The unique ID of the node
The first three elements collectively represent the reference level. A new reference level is defined each time a node loses its last downstream link due to a link failure. The last two values define a delta with respect to the reference level.
Route Creation is done using QRY and UPD packets. The route creation algorithm starts with the height (propagation ordering parameter in the quintuple) of destination set to 0 and all other node’s height set to NULL (i.e. undefined). The source broadcasts a QRY packet with the destination node’s id in it. A node with a non-NULL height responds with a UPD packet that has its height in it. A node receiving a UPD packet sets its height to one more than that of the node that generated the UPD. A node with higher height is considered upstream and a node with lower height downstream. In this way a directed acyclic graph is constructed from source to the destination
When a node moves the DAG route is broken, and route maintenance is needed to reestablish a DAG for the same destination. When the last downstream link of a node fails, it generates a new reference level. Links are reversed to reflect the change in adapting to the new reference level. This has the same effect as reversing the direction of one or more links when a node has no downstream links. In the route erasure phase, TORA floods a broadcast clear packet (CLR) throughout the network to erase invalid routes.
In TORA there is a potential for oscillations to occur, especially when multiple sets of coordinating nodes are concurrently detecting partitions, erasing routes, and building new routes based on each other. Because TORA uses internodal coordination, its instability problem is like the “count-to-infinity” problem in distance-vector routing protocols, except that such oscillations are temporary and route convergence will ultimately occur.
126.96.36.199 ASSOCIATIVITY BASED ROUTING PROTOCOL (ABR)
The Associativity Based Routing (ABR) protocol is a new approach for routing. ABR defines a new metric for routing known as the degree of association stability. It is free from loops, deadlock, and packet duplicates. In ABR, a route is selected based on associativity states of nodes. The routes thus selected are liked to be long-lived. All node generates periodic beacons to signify its existence. When a neighbor node receives a beacon, it updates its associativity tables. For every beacon received, a node increments its associativity tick with respect to the node from which it received the beacon. Association stability means connection stability of one node with respect to another node over time and space. A high value of associativity tick with respect to a node indicates a low state of node mobility, while a low value of associativity tick may indicate a high state of node mobility. Associativity ticks are reset when the neighbors of a node or the node itself move out of proximity. The fundamental objective of ABR is to find longer-lived routes for ad hoc mobile networks. The three phases of ABR are Route discovery, Route reconstruction (RRC) and Route deletion.
The route discovery phase is a broadcast query and await-reply (BQ-REPLY) cycle. The source node broadcasts a BQ message in search of nodes that have a route to the destination. A node does not forward a BQ request more than once. On receiving a BQ message, an intermediate node appends its address and its associativity ticks to the query packet. The next succeeding node erases its upstream node neighbors’ associativity tick entries and retains only the entry concerned with itself and its upstream node. Each packet arriving at the destination will contain the associativity ticks of the nodes along the route from source to the destination. The destination can now select the best route by examining the associativity ticks along each of the paths. If multiple paths have the same overall degree of association stability, the route with the minimum number of hops is selected. Once a path has been chosen, the destination sends a REPLY packet back to the source along this path. The nodes on the path that the REPLY packet follows mark their routes as valid. All other routes remain inactive, thus avoiding the chance of duplicate packets arriving at the destination.
RRC phase consists of partial route discovery, invalid route erasure, valid route updates, and new route discovery, depending on which node(s) along the route move. Source node movement results in a new BQ-REPLY process because the routing protocol is source-initiated. The route notification (RN) message is used to erase the route entries associated with downstream nodes. When the destination moves, the destination’s immediate upstream node erases its route. A localized query (LQ H) process, where H refers to the hop count from the upstream node to the destination, is initiated to determine if the node is still reachable. If the destination receives the LQ packet, it selects the best partial route and REPLY’s; otherwise, the initiating node times out and backtracks to the next upstream node. An RN message is sent to the next upstream node to erase the invalid route and inform this node that it should invoke the LQ H process. If this process results in backtracking more than halfway to the source, the LQ process is discontinued and the source initiates a new BQ process.
When a discovered route is no longer needed, the source node initiates a route delete (RD) broadcast. All nodes along the route delete the route entry from their routing tables. The RD message is propagated by a full broadcast, as opposed to a directed broadcast, because the source node may not be aware of any route node changes that occurred during RRCs.
188.8.131.52 SIGNAL STABILITY ROUTING PROTOCOL (SSR)
Signal Stability-Based Adaptive Routing protocol (SSR) is an on-demand routing protocol that selects routes based on the signal strength between nodes and a node’s location stability. This route selection criterion has the effect of choosing routes that have “stronger” connectivity. SSR comprises of two cooperative protocols: The Dynamic Routing Protocol (DRP) and the Static Routing Protocol (SRP).
The DRP maintains the Signal Stability Table (SST) and Routing Table (RT). The SST stores the signal strength of neighboring nodes obtained by periodic beacons from the link layer of each neighboring node. Signal strength is either recorded as a strong or weak channel. All transmissions are received by DRP and processed. After updating the appropriate table entries, the DRP passes the packet to the SRP.
The SRP passes the packet up the stack if it is the intended receiver. If not, it looks up the destination in the RT and forwards the packet. If there is no entry for the destination in the RT, it initiates a route-search process to find a route. Route-request packets are forwarded to the next hop only if they are received over strong channels and have not been previously processed (to avoid looping). The destination chooses the first arriving route-search packet to send back as it is highly likely that the packet arrived over the shortest and/or least congested path. The DRP reverses the selected route and sends a route-reply message back to the initiator of route-request. The DRP of the nodes along the path update their RTs accordingly.
Route-search packets arriving at the destination have necessarily arrived on the path of strongest signal stability because the packets arriving over a weak channel are dropped at intermediate nodes. If the source times out before receiving a reply then it changes the PREF field in the header to indicate that weak channels are acceptable, since these may be the only links over which the packet can be propagated.
When a link failure is detected within the network, the intermediate nodes send an error message to the source indicating which channel has failed. The source then sends an erase message to notify all nodes of the broken link and initiates a new route-search process to find a new path to the destination.
DESIGN AND IMPLEMENTATION
5.1 APPROACH I-USING WIRED NETWORK
While designing the prototype on Network Simulator, we started with wired network approach.