Issues on Implementing Localisation-based Routing Algorithms

Introduction to this Article.

In fact, this article is a huge one. Without the proper introduction to different technologies, it is impossible to understand the issues of implementing a localization-based routing algorithm for an application area such as the Underwater Wireless Sensor Network(UWSN). A localization-based routing algorithm is nothing but a “Location Based Routing Algorithm” where the Location Information of the nodes will be periodically resolved using a Localization Service.

This article is an outcome of my interaction with research scholars and students for around two decades. Of course, the scope of every research/researcher is to promote the research to another level by innovating something to perform better than the previous one.

But, I often see scholars who are submitting research proposals on Localization-based routing algorithms with some hypothetical, impractical, idiotic ideas that will never lead to a state-of-the-art routing algorithm with ‘improved’ performance, particularly in applications such as UWSN.

Whether this article may help one to correct their previously submitted research proposal or not; certainly, it will help one to be careful while submitting a research proposal, particularly on UWSN.

Localization Algorithms

A localization algorithm is a computational method or set of techniques used to estimate or determine the physical locations of nodes or devices in a network. It is commonly used in wireless sensor networks, ad hoc networks, Internet of Things (IoT) systems, Underwater Networks, and other distributed systems where location information is essential for various applications.

Localization Algorithms and GPS

Localization algorithms and GPS (Global Positioning System) are closely related but differ in their underlying principles and implementations.

Localization algorithms, as mentioned earlier, are computational methods used to estimate the physical locations of nodes or devices in a network. These algorithms can utilize various techniques such as range-based measurements, proximity-based information, angle of arrival, time of flight, or fingerprinting to estimate node positions. Localization algorithms are commonly used in wireless sensor networks, ad hoc networks, and other systems where accurate location information is necessary.

On the other hand, GPS is a specific global navigation satellite system that provides positioning, navigation, and timing services worldwide. GPS relies on a network of satellites orbiting the Earth and ground-based receivers to determine precise geographic coordinates. GPS receivers receive signals from multiple satellites and use trilateration techniques to calculate their own positions based on the time it takes for signals to reach them from different satellites.

While localization algorithms can use GPS as a source of location information, they are not limited to GPS alone. Localization algorithms can work with a variety of other measurements, such as signal strengths, distances, angles, or connectivity information, depending on the available infrastructure and network characteristics. In environments where GPS signals may be weak or unavailable, localization algorithms can rely on alternative sources of information such as Wi-Fi signals, cellular networks, or environmental sensing to estimate positions.

It’s worth noting that GPS is a well-established and widely used positioning system, particularly for outdoor environments. However, it may face challenges in indoor or urban environments with obstructions that can attenuate or block satellite signals. In such cases, localization algorithms that incorporate other sensing techniques or infrastructure (e.g., Wi-Fi fingerprinting, Bluetooth beacons) can complement or replace GPS to provide accurate positioning information.

Localization of Nodes in Underwater Networks

GPS does not work underwater. GPS works by using radio signals to communicate with satellites in space. However, water absorbs radio waves, so the radio signals from GPS satellites cannot penetrate water very far. Theoretically, GPS signals can penetrate to a few meters only. Further, receiving such weak signals underwater will be a challenging task.

There are a number of other technologies that can be used for underwater positioning, including:

Acoustic positioning: Acoustic positioning systems use sound waves to measure the distance between a device and known points. This is the most common type of underwater positioning system.
Lidar positioning: Lidar positioning systems use laser beams to measure the distance between a device and known points. This is a more accurate type of underwater positioning system, but it is also more expensive.
Inertial navigation systems: Inertial navigation systems use a combination of accelerometers, gyroscopes, and magnetometers to track the movement of a device. This is a less accurate type of underwater positioning system, but it is also less expensive.

The best type of underwater positioning system for a particular application will depend on the specific requirements of the application. For example, if accuracy is critical, then a lidar positioning system may be the best option. However, if cost is a major consideration, then an inertial navigation system may be a better option.

But, designing a Localization algorithm for an underwater network will be a challenging task. For example, if we assume anchor nodes based triangulation algorithm, the location of the anchor nodes itself will be very unreliable in underwater conditions because of the drifts of the nodes due to underwater currents and movement.

Message Overheads in Time Synchronization and localization algorithms

Both time synchronization and localization algorithms can introduce message overheads in networked systems. These overheads are incurred due to the exchange of control messages and coordination among network nodes. Here are some of the message overheads commonly associated with time synchronization and localization algorithms:

A. Time Synchronization:

Time Request Messages: In distributed time synchronization algorithms, nodes often exchange time request messages to initiate the synchronization process. These messages are sent from the nodes requesting time synchronization to the reference nodes or time servers.
Time Response Messages: Reference nodes or time servers respond to time request messages by sending time response messages containing their synchronized time information. These messages are received and processed by the requesting nodes.
Time Update Messages: Nodes may exchange time update messages to disseminate synchronized time information throughout the network, ensuring that all nodes maintain a consistent notion of time.
Control and Coordination Messages: Sometimes synchronization algorithms may require additional control or coordination messages to manage the synchronization process, handle clock drift, or adjust synchronization parameters.

B. Localization:

Beacon Messages: Localization algorithms often utilize beacon messages transmitted by reference nodes with known positions. These messages contain information about the reference node’s identity and position. Nodes in the vicinity receive and process these beacon messages to estimate their own positions.
Measurement Messages: In range-based localization algorithms, nodes may exchange measurement messages containing distance or range information. These messages are used to estimate the positions based on ranging techniques such as received signal strength (RSS) or time of flight (ToF).
Neighbor Discovery Messages: Some localization algorithms require nodes to exchange neighbor discovery messages to gather information about the surrounding nodes, their identities, and potentially their positions. This information aids in position estimation and network coordination.
Localization Update Messages: Localization algorithms that involve iterative estimation or tracking may require nodes to exchange localization update messages to refine and improve the position estimates over time.
Control and Synchronization Messages: Certain localization algorithms may rely on control or synchronization messages to coordinate the positioning process, handle node mobility, or adjust algorithm parameters.

These message overheads can consume network bandwidth, introduce latency, and impact energy consumption, particularly in resource-constrained networks or systems with a large number of nodes. Balancing the need for accurate synchronization or localization with the associated message overheads is an important consideration when designing and implementing such algorithms. Efficiency improvements, optimization techniques, and protocol design choices can help mitigate the impact of message overheads on overall system performance.

Localization Algorithms and Techniques

Localization algorithms can employ different techniques and approaches based on the available resources and network characteristics. Here are a few commonly used localization algorithms:

Range-based Localization: This type of algorithm uses distance or range measurements, such as received signal strength (RSS) or time of arrival (ToA), to estimate node positions. Trilateration, triangulation, or multilateration techniques are often employed to calculate node locations based on the measured ranges.
Range-free Localization: These algorithms do not rely on direct distance or range measurements but instead use connectivity or neighborhood information. Examples include hop-count-based localization, where the distance between nodes is estimated based on the number of hops required to reach a reference node.
Proximity-based Localization: This algorithm exploits the relative proximity of nodes to estimate their locations. It leverages the signal strength of nearby nodes or the presence of anchor nodes with known positions to infer the location of other nodes.
Angle of Arrival (AoA) Localization: This technique estimates node positions based on the angles at which signals arrive at the nodes. Multiple angle measurements from different reference points can be used to determine the positions using geometric calculations.
Time of Flight (ToF) Localization: This algorithm utilizes the time taken for signals to propagate between nodes to estimate distances and subsequently determine node positions.
Fingerprinting Localization: Fingerprinting algorithms create a database of pre-measured signal strength or other environmental attributes at known locations. Nodes can then compare their observed signal characteristics with the database to determine their location.
Distributed Localization: These algorithms involve collaborative efforts among nodes to collectively estimate their positions. Each node may exchange information with its neighbors and perform calculations to achieve a global view of the network and its location distribution.

The choice of a localization algorithm depends on factors such as network topology, available resources (e.g., hardware capabilities, power constraints), accuracy requirements, and deployment scenarios.

Challenges in Implementing Localization-based Routing Algorithms

Implementing localization-based routing algorithms can pose several challenges. Here are some common issues that can arise during the implementation process:

Localization Accuracy: Localization-based routing algorithms rely on accurate location information of the network nodes. However, achieving precise localization in real-world scenarios can be challenging. Factors such as signal interference, multipath fading, and non-line-of-sight conditions can introduce errors in location estimation. These inaccuracies can impact the effectiveness of routing decisions and lead to suboptimal performance.
Scalability: Localizing a large number of network nodes can be computationally intensive and may require significant processing power and memory resources. As the network size increases, the overhead associated with localization can become a bottleneck. Implementing scalable localization algorithms that can handle a large number of nodes efficiently is crucial for practical deployments.
Mobility Support: Localization-based routing algorithms should be able to handle node mobility effectively. When nodes move, their locations change and routing decisions based on outdated information can lead to routing failures or suboptimal paths. Incorporating mechanisms to track and update node locations in real-time, as well as handling location updates efficiently, is important for maintaining routing performance in dynamic environments.
Energy Efficiency: Localization algorithms often require nodes to actively participate in the localization process, which can consume significant energy. This energy consumption can be problematic, especially for resource-constrained devices or wireless sensor networks where energy conservation is crucial. Balancing the need for accurate localization with energy efficiency is a key challenge in implementing localization-based routing algorithms.
Security and Privacy: Localization information can be sensitive and potentially reveal the physical locations of network nodes. Ensuring the security and privacy of localization data is essential to prevent malicious attacks or unauthorized access. Implementing secure mechanisms for location estimation, data transmission, and storage is critical to protect the integrity and confidentiality of location information.
Robustness to Environmental Conditions: Localization-based routing algorithms may encounter environmental conditions that can affect the reliability of location estimation. Factors such as obstacles, terrain characteristics, or adverse weather conditions can impact the accuracy of localization systems. Robustness against such conditions is important to maintain reliable routing performance in diverse environments.
Implementation Complexity: Localization algorithms often involve complex mathematical models and require sophisticated techniques for data fusion, signal processing, and estimation. Implementing these algorithms correctly can be challenging, especially for developers without a strong background in signal processing or localization techniques. Adequate expertise and resources may be necessary to implement localization-based routing algorithms effectively.

Addressing these challenges requires careful consideration of system requirements, algorithm design, and implementation techniques. Thorough testing and evaluation in realistic scenarios can help identify and mitigate issues before deployment. Additionally, staying informed about advancements in localization and routing technologies can provide insights into potential solutions and best practices.

Paper-ware Publications on Localization-based Routing Algorithms.

There are a number of fake research publications or paper-ware[1] publications on localization-based routing algorithms that often make unrealistic claims about the performance of the algorithms, and they may not be based on any real-world implementation.

Here are some examples of paper-ware publications on localization-based routing algorithms:

A paper that claims to have developed a new localization-based routing algorithm that is 100% accurate. This is an unrealistic claim, as no localization algorithm can be 100% accurate.
A paper claims to have developed a new localization-based routing algorithm that can route packets in real-time with zero latency. This is also an unrealistic claim, as there is always some latency involved in routing packets.
A paper that claims to have developed a new localization-based routing algorithm that provided more throughput and pdf without increasing other message overheads. This is an unrealistic claim, because, due to the parallel implementation of time synchronization and localization (along with the routing logic), there is no way to reduce the message overhead.
A paper that claims to have developed an ML/AI/RL framework to optimize the performance of localization algorithm and route discovery under a mobile underwater sensor network and achieved better performance in terms of PDF and e2e delay without increasing the message overhead.

If you are reading a paper on localization-based routing algorithms, it is important to be aware of the possibility that the paper may be fake or paper-ware. You should look for the following signs to identify fake research publications or paper-ware publications:

The paper makes unrealistic claims about the performance of the algorithm.
The paper was not from a reputable journal or conference.
The paper is not well-written or organized.
The paper does not provide any implementation details or performance results.
The paper is based on unrealistic assumptions.
The papers makes unrealistic claims.

Scholars will imagine things based on some ‘false theoretical’ understanding and based on some facts that they may find in published papers. If one carefully explores, then one can understand that such papers did not publish any related code because of obvious reasons[6].

Will it be Hard to Implement One Such Algorithm?

As far as I searched, the following (from [4] and [5]) are the genuine answer from an ‘ns-3 developer’ that explains the complexities involved in the design of a localization algorithm under a simulator.

Tommaso Pecorella
Nov 19, 2015, 4:29:13 PM
to ns-3-users

Hi,

let me clarify some points about localization and ns-3, as it seems that there’s something that is not understood at all.

Nodes in ns-3 knows their exact position and the exact time.

Localization is all about having an imperfect knowledge of position and time.

You understand now what is the problem ?

Time: we recently added some functions to have a per-node clock, each one with its own precision. The functionality is still at extremely early stage, and right now the API is just a wrapper around the “old” absolute time. As a consequence, one should first fill this gap. Any contribution is welcome.

Position: as for time, node position is down by nodes exactly. However, one should add a imperfect knowledge layer, e.g., one taking into account the relative error of GPS, or something similar.

MOREOVER, localization techniques are affected by non-deterministic delays in signal processing. I.e., when you receive a signal a node could have an internal random processing delay on top of the fixed and known part. This adds to the localization precision outcomes. If you don’t add this too, your results will be flawed. Note that processing delay is not modeled at all in ns-3.

Summarizing: good luck. It is possible to simulate localization using ns-3, but you should have a deep understanding of the whole problem and of the limits / restrictions of the simulation environment. Fail at one small bit and your results are invalid.

Have fun.

T.

PS: the above considerations apply to Matlab too, and any other simulation environment.

Tommaso Pecorella

Nov 19, 2015, 6:33:28 PM

to ns-3-users

It is evident that I wasn’t clear in my previous message.

I am not aware of any localization method implemented in ns-3, and (as i pointed out) it will very hard to make one.

T.

Think About the Following

If you are planning to use a simulator for doing your UWSN protocol-related research, particularly localization-based UWSN routing protocol, before starting to submit your research proposal, ask yourself the following questions and try to answer the questions on your own:

Have you really know anything practical about Acoustic Underwater Network Simulation?
Have you realized the insignificant capability of an Acoustic Modem or UW networking device?
Have you really examined any implementation of alternate technologies such as underwater visual light communication (VLC) technology?
Have you simulated any simple UWSN in any network simulator?
Have you tested any existing UWSN routing protocol under any network simulator?
Have you really tested any existing UWSN mobility models under any network simulator?
Have you implemented or tested any existing localization algorithms under any network simulator?
Have you implemented or tested any existing time synchronization algorithms under any network simulator?
Have you evaluated the existing UWSN routing algorithms with and without a simple localization model?
Have you evaluated the existing UWSN MAC algorithms with and without a simple localization model?
Have you ever used any performance metrics to measure the performance of UWSN algorithms (MAC, Routing, etc., layer performance)?
Have you ever used any energy models to measure the performance of a UWSN in terms of energy?
Do you really think that your implementation of localization-based UWSN routing protocol will perform better than VBF, DBR, or even the Underwater Flooding?

The above questions and your answers to them will help you to understand your present knowledge of the problem that we are facing here. It will help you to estimate your skills and make you understand the skills that may be needed to really implement a localization-based UWSN routing protocol.

Possibilities of Implementing a Localization-based UWSN Routing Protocol

While implementing a novel algorithm, we will expect it to work better than an existing algorithm, But, implementing a localization algorithm inside a UWSN routing protocol will increase the message overhead considerably. Because, for example, we need to broadcast some beacons in a periodic fashion to share the locations of the anchor nodes. In addition to that, we need to do some periodic broadcasts to maintain time synchronization. The routing protocol itself may periodically broadcast some packets for route discovery and routing table maintenance. – all of these message broadcasts will increase the message overhead and will lead to poor performance. In addition to that it may drain the battery of the UWSN node very rapidly.

So, if we try to implement a localization-based DBR routing protocol, practically, our new localization-based DBR may perform poorly than the standard DBR in terms of energy consumption and some other performance metrics.

So, how it will be possible to really devise a better UWSN routing protocol by incorporating localization algorithm in it?

Conclusion

I am not claiming that the implementation of one such genuine, perfect of localization-based UWSN routing protocol is not possible. Just I am trying to make the researchers to realize the complexity in design one such theoretically correct algorithm. Another big question here is: even if we implement one such localization-based UWSN routing protocol, will it really be able to compete with simple UWSN routing algorithms such as DBR or UW Flooding? This is the big question that I am leaving here for the imagination of the researchers.