mobile sink and routing algorithm in WSN

[Long Le]

Dear all,

I'm a student in Computer science. I'm doing a thesis about the routing algorithm in WSN. I want to implement an algorithm which can combine Unmanned Vehicle working as a mobile sink in a wireless sensor network. I'm looking for a code for shortest path in routing protocols such as: Dijkstra's algorithm, SHORTEST, etc.

I would like to combine 2 algorithms into an hybrid one and let see it can improve something.

Any help or suggestion, I am appreciate.

Thank you.

Long Le

[Tommaso Pecorella]

Hi,

I guess you need some clarifications about routing (in general). Perhaps your preparation is a bit too academic and your teachers "forgot" to tell you some nasty parts.

For the sake of other readers, I'll go full academic on this, sorry in advance.

Real Routing is made by 4 main parts:

1) The algorithms calculating the shortest "path" (who wants to take a longer one ?) - note that by "shortest" I mean a full set of things, more later.

2) A protocol, needed to exchange data for the routing protocol (e.g., number of hops, remaining node energy, link quality, etc.).

3) Data structures in the node (memory management).

4) Some assumptions on the scenario the protocol is used for.

The 3 elements can not really be split, as a choice on one could affect what you can do on the other points.

As an example, you can not apply Dijkstra on RIP, because RIP is a distance vector protocol, meaning that 1) the protocol only exchanges data with the 1-hop neighbors and 2) the data stored is very limited. As a consequence, it lacks the topology knowledge needed to run Dijkstra. It will reach a shortest path but using a Bellman-Ford approach, which is much slower. However, this is not a problem because the scenario is the one of a network with slow changes.

Now, you named one algorithm (Dijkstra), dunno about the other - if it's a protocol the authors did choose a very bad name.

What you should do is:

1) decide the scenario. Are the nodes mobile ? How much mobile with respect to the routes updates ? It is worth to do a proactive or a reactive routing ?

2) define a metric - shortest is the number of hops or you want to consider also other elements, like the drop probability and the link bandwidth ?

3) study a protocol to support the above two things - data have to be exchanged between the nodes to be used for routing decisions.

4) the easy part: apply an algorithm to find te best next hop (or the best path).

Point 4 is piss easy, there are a lot of open source implementations for Dijkstra and such. The real problem lies in the first 3 points.

Another suggestion is: study the literature. Routing is a rather well studied subject. You can (o course) propose many new things, but there's still a lot of knowledge that should be... known.

Cheers,

T.

[Long Le]

Thank you so much for your comment Professor,

My working thesis is basically want to apply unmanned vehicle to become a mobile sink (I will do multiple uvs in the future). Right now just want to test on one sink and fixed number of nodes. In order to try to solve energy hole in WSN (a static sink may run out of energy very fast), I want to apply mobile sink algorithm. The general idea is that use the uv run on the shortest path which cover each node to collect data. If the battery on the uv run below the theasure, use another algorithm to colect the head cluster of node. By this way, it might improve the energy as well as the coverage by using a single mobile sink. There are some paper that I have read and very interested in such as:
An energy-efficient mobile-sink path selection statergy for WSNs.
Some routing algorithms in WSNs.

Please get me through.

Thank you,

Long Le

[Tommaso Pecorella]

Hi,

well, this is completely different from what I had in mind. Here you're not talking about "classical" routing for a connected graph, here you have a DTN, where you have a sink (your UV) collecting data from single nodes or a whole cluster of nodes (through the cluster head).

Let me say: the topic is interesting, but it's a hell of a topic. In order to simulate it correctly you'll need a number of points to be considered, and all of them could potentially affect a LOT the performance of your system.

As an example: the time and energy needed for the nodes to pair with the mobile UV is important. The UV will need to stay in radio range of each node its communicating with for enough time to gather the data, etc.

Summarizing, you'll need a very good scenario, and you also need to identify what are the current ns-3 models limitations before coding.

Once you have these points fixed, the actual algorithm seems to be (again) quite hellish: check the https://en.wikipedia.org/wiki/Travelling_salesman_problem

Anyway, your algorithm should be (at the end) tied with the mobility model, not with routing.

However you'll also need all the parts of node association / disassociation, data upload, etc. Most of them are not available in ns-3, but they can be developed.

Again, the suggestion is to elaborate and fix your scenario, find the required features you need to have in your simulation, check if they are all available in ns-3 and (eventually) develop what's missing.

Cheers,

T.

[Long Le]

Thank you,

Can you have me with any website that share the ns3 code for simulating mobile node in any particular algorithm. 

I honestly have to start from 0. 

Thank you so much,

Long Le

[Tommaso Pecorella]

Hi,

I'd suggest to start from the mobility model:

https://www.nsnam.org/docs/models/html/mobility.html

T.

[Long Le]

Thank you, 

I have problem with the visualizer function.

I want to generate the .xml file which can be opened by netanim. I want to see the graphic of random-wayponit module example to see how it works but I don't know how to generate graphic file. 

I've looked in the internet and see several ways to do it. But my question is is there any common and easy way to generate this file.

Moreover, If I want to modify the waypoint (not the random waypoint) to a particular algorithm, what should I do?

Thank you,

Long Le

[Tommaso Pecorella]

Hi,

as far as I know, the lr-wpan model is not yet supported by NetAnim. it shouldn't be hard to add support for it tho.

About the waypoint question, mind to explain the problem a bit better ?

Cheers,

T.

[Long Le]

Hi all, my thesis is almost finish. Thanks for your helping.

Now quick question. I want to calculate the algorithm running time to show on the graph. Is it based on the complexity of the alogoirthm?

This is piece of my algorithm code

void remaining energy (double old value, double, remainingEnergy)

{

            computeShortestPath(graph, 0); //Dijiktra's algorithm                           à nlog(n)

            if (remainingEnergy < threshold && remainingEnergy > bfdrainoutbattery)

            {

                        while (remainingunvisitednode)

{

            WRP based algorithm;// Weight  Rendezvous Planning algorithm                        à log(n)

}

            }

            else return home;

}

How can I calculate the complexity of this algorithm? I am doing it right?

Thank you.

[Tommaso Pecorella]

Hi,

I'm glad you're close to the thesis end.

About the question, the problem is to define what's "algorithm running time". A Dijiktra's algorithm running time depends on the CPU speed, the memory architecture and so on. These things (any processing time, indeed) are not simulated in ns-3. The only time-consuming thing simulated in ns-3 is packet transmission and reception. As a side note, we discussed more than once why this is so. It is a design choice and there are a lot of reasons for it.

I don't know if your WRP based algorithm is like Dijiktra's, in the sense that it works on already acquired data, or if it needs some network activity. In the latter case you could try to measure the time needed to run the algorithm, but... but. See below.

Problem: how to define an algorithm running time ?

Option 1: the algorithm is communication-bound (like IO-bound, but for network). You can use a simulator and a LOT of statistical analysis.

Option 2: the algorithm is CPU-bound. You *could* measure it, but it would be a huge mistake, as the results will depend on the particular architecture AND on your specific implementation. It is wiser to calculate the upper bound (e.g., n log(n)) and check how many comparisons / multiplications / addition / etc. are needed in each step. Then do the math.

If, like in your case, you have a mixed mode algorithm, you can do some stats on the node parameters to say that your nodes energy is a given percentage at a given time, then do the math. basically a mic between simulations (to have the number of nodes at a given energy in a given time) and math (to know the algorithm complexity).

Hope this helps,

T.

PS: I have no idea on how your nodes could use two different routing algorithms. They'd need a common packet format... bah, it's your thesis, not mine.

[Vishnuvarthan Rajagopal]

Hi,

I am very much interested in this work and about to start them from the scratch. It will be more helpful if I could get your code for understanding and starting at this point. If possible may you please share your code?

Thank you in advance.