Random Walks with Tabu Lists in Routing Algorithms

routing algorithms using random walks with tabu l.w
1 / 35
Embed
Share

Discover the innovative use of random walks with tabu lists in routing algorithms for wireless sensor networks. Explore the benefits, comparisons, and implications of this approach, presented in a synchronized meeting on 22/02/11.

  • Routing Algorithms
  • Random Walks
  • Tabu Lists
  • Wireless Sensor Networks
  • Synchronized Meeting
rayaanacharya
gilda Follow

Uploaded on | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Routing Algorithms using Random Walks with Tabu Lists Karine Altisen & St phane Devismes Joint work with Antoine Gerbaud, Pascal Lafourcade, and Cl ment Ponsonnet ARESA 2

  2. Disclaimer Today, we will speak about probabilities But, we are not specialists 22/02/11 Meeting Synchrone 2

  3. Wireless Sensor Network (WSN) Sensor(s) Processor Radio Battery 22/02/11 Meeting Synchrone 3

  4. Routing 22/02/11 Meeting Synchrone 4

  5. Application 22/02/11 Meeting Synchrone 5

  6. Setting One sink/Multi source Connected 8 4 7 3 Identified 5 Reliable 9 1 Asynchronous 6 2 Spontaneous requests 22/02/11 Meeting Synchrone 6

  7. Random Walk 8 4 7 3 5 9 1 Rand(9,8,6,4,3) Rand(1,7,5,6,2) 6 Rand(7,9,2) 2 Rand(1,9,6) 22/02/11 Meeting Synchrone 7

  8. Probability Laws Uniform (RW) Let v,u two neighbors, v u Problem: hitting time = O(N3) 22/02/11 Meeting Synchrone 8

  9. Probability Laws Biased (Yamashita et al) (RWLD) Let v,u two neighbors, v u standardize frequencies of visits, for all nodes hitting time = O(N2) 22/02/11 Meeting Synchrone 9

  10. RW vs. RWLD 22/02/11 Meeting Synchrone 10

  11. Routing by Random Walk Pros Message length Tight local computation and memory No need of overlay Load of the network Cons Hitting time (average number of hops to reach the sink) O(N3) (RW) and O(N2) (RWLD) 22/02/11 Meeting Synchrone 11

  12. Random Walk with Tabu Lists Add memory to help random walks Avoid cycles Store hints about previous choices k where k is small Good trade-off ? 22/02/11 Meeting Synchrone 12

  13. Where ? Messages Store IDs of visited nodes Visit new nodes first Nodes One list per destination Store message ID Detect cycles cycle detections: visits 22/02/11 Meeting Synchrone 13

  14. Full ? (Update policy) FIFO policy Rand policy 22/02/11 Meeting Synchrone 14

  15. FIFO Policy Update(e,L) a b e d a b d e e a b f d g z 22/02/11 Meeting Synchrone 15

  16. Rand Policy Update(e,L) a b d e a b f d g z e Rand 22/02/11 Meeting Synchrone 16

  17. Sum up Probability law: RW / RWLD Tabu Lists Location: node / message Tabu List size Update policies: FIFO / Rand 22/02/11 Meeting Synchrone 17

  18. Tabu List in Messages (TLM) 8 4 7 3 5 9 [2,9] [9,5] 1 Rand(8,6,4,3) = 3 [1,2] [2,9] Rand(7,5,6)=5 6 Rand(7,9,2)=2 [1] 2 [1] [1,2] Rand(9,6) = 9 22/02/11 Meeting Synchrone 18

  19. Tabu List & Counters in Nodes (TLCN)(1/2) 1 (12,1) (12,1) (23,8) (23,8) 12 1 (23,8) 1 2 (12,1) (23,8) 22/02/11 Meeting Synchrone 19 1 2 1

  20. Tabu List & Counters in Nodes (TLCN)(2/2) Next destination ? 22/02/11 Meeting Synchrone 20

  21. Experimentations (settings) Sinalgo (JAVA) Graphs: UDG, connected, one sink/multi-source, uniform distribution 100 messages per sources Data generation: [400..600] Transmission time: [40..50] List sizes: TLM: 1 & 15 TLCN: 15 Random Walk: RWLD Update: FIFO & Rand 22/02/11 Meeting Synchrone 21

  22. Hitting time (1/2) 22/02/11 Meeting Synchrone 22

  23. Hitting time (2/2) 22/02/11 Meeting Synchrone 23

  24. Volume, e.g., sum |messages| 22/02/11 Meeting Synchrone 24

  25. Convergence of TLCN 22/02/11 Meeting Synchrone 25

  26. Sum up Degree Sensitivity Load Hitting Time Volume Sensitivity TLCN (15,FIFO) 1 1 no yes TLCN (15,Rand) 1 1 no yes TLM (15,FIFO) 3 7 no no TLM (15,Rand) 4 8 no no TLM (1,FIFO) 5 5 no no TLM (1,Rand) 6 6 no no RWLD 7 3 no no 22/02/11 RW 8 Meeting Synchrone 4 yes no 26

  27. Analysis 22/02/11 Meeting Synchrone 27

  28. NSC for TLM NSC: update rule finite average hitting time If the list is full and the current node is not in the list, then the probability of removing the oldest element is positive FIFO and Rand match the NSC 22/02/11 Meeting Synchrone 28

  29. RW+TLM vs. RW (1/2) |List| 3, there exist graphs where RW is better than RW+TLM Ex. for 4 22/02/11 Meeting Synchrone 29

  30. RW+TLM vs. RW (2/2) |List| = 1,2, RW+TLM is always better than RW 2 3 9 7 4 1 RW+TLM RW 22/02/11 Meeting Synchrone 30

  31. RWLD+TLM vs. RWLD (1/2) For all size, there exist graphs where RWLD is better than RWLD+TLM |List| 3, as previously 2, to be done ! 1: 22/02/11 Meeting Synchrone 31

  32. RWLD+TLM vs. RWLD (2/2) Conjecture: In random graphs, RWLD+TLM is always better than RWLD 22/02/11 Meeting Synchrone 32

  33. RW+TLM 1,2 vs. RWLD (2/2) There exist graphs where RWLD is better than RW+TLM 22/02/11 Meeting Synchrone 33

  34. TLCN Is the hitting time finite ? In case +asynchronous, no Sink 1 Source 22/02/11 Meeting Synchrone 34

  35. Thank you 22/02/11 Meeting Synchrone 35

Related


No related presentations.

More Related Content