Autonomous Virtual Mobile Nodes

0 comments

file time: 2008-03-11

file siez:399.5KB

filetype:ppt

Click Here To Download...

>  

Autonomous Virtual Mobile Nodes 

Shlomi Dolev              Seth Gilbert

Elad Schiller      Alex Shvartsman

Jennifer Welch

 

Challenges 

Locality   Nodes only send messages to nearby nodes Global coordination is expensive   Locality Unreliable nodes   Mobile nodes fail, go to sleep, and get turned off.  

Challenges 

Locality Unreliable nodes Irregular motion   Nodes travel wherever they want to go    Locality Unreliable nodes   Mobile nodes fail, go to sleep, and get turned off.  

Opportunities 

Broadcast   Wireless broadcast is a powerful primitive.   Allows a node to reach all nearby nodes, Ensure they receive the same messages.   

Opportunities 

Broadcast Time & Geography   Nodes are physical entities physical time & location Use GPS and/or algorithms for synchronization / location  

Related work 

Existing protocols   Flooding Distributed structure E.g., TORA [PC97] Compulsory movement of nodes [HP99, CNS01]  

Related work 

Existing protocols Random walk   Random walk of a single agent Coping with chaos by chaos  

Related work 

Existing protocols Random walk Virtual nodes   Geo-Quorums [DGL03] Virtual Stationary Automata [DGL05] Virtual Mobile Node [DGL04]  

Autonomous Virtual Mobile Node 

Automaton   New programming abstraction   A virtual general-purpose computing entity.  

Autonomous Virtual Mobile Node 

Automaton   New programming abstraction Distinct location at any time   Implemented by 00eal000 mobile nodes that happens to be near.  

Autonomous Virtual Mobile Node 

Automaton   New programming abstraction Distinct location at any time   Communicates with: other virtual nodes, and 00eal00mobile nodes.  

Autonomous Virtual Mobile Node 

Automaton Reliability   Fault  recovery   The group emulation enhances robustness: some may fail, or move out of range.   Automaton Reliability   Fault  recovery Self-stabilization   Tolerate any starting state: maybe several (undesired) copies, or none at all.   Automaton Reliability Autonomous   On-line movement decision: current state, and sensor/environment input.  

Example 1

If north-east area appears deserted go south-west  

Autonomous Virtual Mobile Node 

Automaton Reliability Autonomous   On-line movement decision: current state, and sensor/environment input.  

Example 2

Hitchhike with the traffic, or Go in the opposite direction  

Application Domain 

Vehicular networks   Traffic control and safety E.g., ad hoc traffic light  

Application Domain 

Vehicular networks   Traffic control and safety E.g., ad hoc traffic light  

Application Domain 

Vehicular networks RFID tags   Very small, cheap and wireless tagging network. Limited power supply. Photoelectric gate   Use flash light to activate the net The AVMN follows the light E.g., count the number of items find an expired item Use microwave instead of light.  

Application Domain 

Vehicular networks RFID tags Swarm computing   Multiple virtual nodes Hierarchically originated Performing different task Collaborating or competing  

Implementation 

Exactly 1 instance  

Three different schemes

Virtual Stationary Automaton   alive messages to known location

of a stationary node (VSA)

VSA keeps track of the AVMN No message for too long create a new AVMN VSA eliminates duplicates  

Implementation 

Exactly 1 instance  

Three different schemes

Virtual Stationary Automaton Send alive messages   Send alive messages in a random walk fashion.   If a real node doesn00 receive an alive message for too long generates a formation token carries ids and traverses in a random walk fashion If tokens collide: merge ids00lists  

If containing more than (N+1)/2

creates a new AVMN  

Implementation 

Exactly 1 instance  

Three different schemes

Virtual Stationary Automaton Send alive messages Nodes alive messages   Real nodes periodically send stay alive messages random walk to AVMN in order to survive AVMN must collect at least (N + 1)/2 messages.  

Implementation 

Exactly 1 instance Self-stabilization   Every emulating real node Keeps a replica of the AVMN Ensures identical replica   Buffer input events waiting to be applied to the state. At a fixed interval, sends replica to all. Predetermined function resolves conflicts.  

<State3, input3> 

<State2, input2> 

<State1, input1> 

<State3, input3> 

<State2, input2> 

<State1, input1> 

<State3, input3> 

<State2, input2> 

<State1, input1> 

<State2, input2> 

<State1, input1>

 

Implementation 

Exactly 1 instance Self-stabilization Mobility   Where and when to move? Can be decided  by current state Ensure the right order of events Ensure nodes麓 proper join/leave     

x1 

x2 

x3 

move to x2 on t2 

move to x3 on t3 

<join, id 37634>  

<State, input> 

Esure that: Old nodes remain participants Enough nodes near the new location can receive notification And, mobile nodes can join  

Discussion  

Described how to implement a single AVMN Can implement multiple AVMNs using the same techniques. There are a number of ways to optimize Use min amount of power to reach everyone. Use nodes that are closer to the new AVMN centrum. If possible, take advantage of nodes movement.  

Thank you 

Your attention is appreciated

   download Autonomous Virtual Mobile Nodes