|
Wiselib
|
wiselib.testing/algorithms/routing/lazy/lazy.h
Go to the documentation of this file.
00001 /*************************************************************************** 00002 ** This file is part of the generic algorithm library Wiselib. ** 00003 ** Copyright (C) 2008,2009 by the Wisebed (www.wisebed.eu) project. ** 00004 ** ** 00005 ** The Wiselib is free software: you can redistribute it and/or modify ** 00006 ** it under the terms of the GNU Lesser General Public License as ** 00007 ** published by the Free Software Foundation, either version 3 of the ** 00008 ** License, or (at your option) any later version. ** 00009 ** ** 00010 ** The Wiselib is distributed in the hope that it will be useful, ** 00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** 00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** 00013 ** GNU Lesser General Public License for more details. ** 00014 ** ** 00015 ** You should have received a copy of the GNU Lesser General Public ** 00016 ** License along with the Wiselib. ** 00017 ** If not, see <http://www.gnu.org/licenses/>. ** 00018 ***************************************************************************/ 00019 #ifndef __LAZY_H__ 00020 #define __LAZY_H__ 00021 #include "util/base_classes/routing_base.h" 00022 #include "lazy_message.h" 00023 00024 namespace wiselib 00025 { 00036 template< typename Os_P, 00037 typename Radio_P, 00038 typename Timer_P, 00039 typename Rand_P, 00040 typename Node_P, 00041 typename NodeList_P, 00042 typename Connectivity_P, 00043 typename ConnectivityList_P, 00044 typename Debug_P> 00045 class LazyType 00046 : public RoutingBase<Os_P, Radio_P> 00047 { 00048 public: 00049 typedef Os_P Os; 00050 typedef Radio_P Radio; 00051 typedef Timer_P Timer; 00052 typedef Rand_P Rand; 00053 typedef Debug_P Debug; 00054 typedef Node_P Node; 00055 typedef NodeList_P NodeList; 00056 typedef Connectivity_P Connectivity; 00057 typedef ConnectivityList_P ConnectivityList; 00058 typedef LazyType<Os, Radio, Timer, Rand, Node, NodeList, Connectivity, ConnectivityList, Debug> self_type; 00059 typedef typename NodeList::iterator NodeListIterator; 00060 typedef typename ConnectivityList::iterator ConnectivityListIterator; 00061 typedef typename Node::Position Position; 00062 typedef typename Node::Position::CoordinatesNumber CoordinatesNumber; 00063 typedef typename Radio::node_id_t node_id_t; 00064 typedef typename Radio::size_t size_t; 00065 typedef typename Radio::block_data_t block_data_t; 00066 typedef typename Radio::message_id_t message_id_t; 00067 typedef typename Timer::millis_t millis_t; 00068 typedef LazyMessageType<Os, Radio> Message; 00069 00070 // -------------------------------------------------------------------- 00071 enum ErrorCodes 00072 { 00073 SUCCESS = Os::SUCCESS, 00074 ERR_UNSPEC = Os::ERR_UNSPEC, 00075 ERR_NETDOWN = Os::ERR_NETDOWN 00076 }; 00077 // -------------------------------------------------------------------- 00078 enum SpecialNodeIds 00079 { 00080 BROADCAST_ADDRESS = Radio_P::BROADCAST_ADDRESS, 00081 NULL_NODE_ID = Radio_P::NULL_NODE_ID 00082 }; 00083 // -------------------------------------------------------------------- 00084 enum Restrictions 00085 { 00086 MAX_MESSAGE_LENGTH = Radio_P::MAX_MESSAGE_LENGTH - Message::PAYLOAD_POS 00087 }; 00088 // -------------------------------------------------------------------- 00089 00090 LazyType(); 00091 ~LazyType(); 00092 void enable( void ); 00093 void disable( void ); 00094 uint8_t decision_lazy( Node, node_id_t ); 00095 void send_neighbor_discovery( void* ); 00096 void send_vicinity_discovery( void* ); 00097 void send_greedy( void* ); 00098 void send( node_id_t, size_t, block_data_t*, message_id_t ); 00099 void receive( node_id_t, size_t, block_data_t* ); 00100 void store_neighbor( Node ); 00101 void store_vicinity( Connectivity ); 00102 void print_neighbors( void* ); 00103 void print_vicinity( void* ); 00104 void filter_vicinity( void* ); 00105 void init( Radio& radio, Timer& timer, Debug& debug, Rand& rand ) 00106 { 00107 radio_ = &radio; 00108 debug_ = &debug; 00109 timer_ = &timer; 00110 rand_ = &rand; 00111 } 00112 inline void set_self( Node _n, NodeList _nl ) 00113 { 00114 self.set_node(_n ); 00115 self.set_vicinity_list( _nl ); 00116 } 00117 inline void set_self( Node _n ) 00118 { 00119 self.set_node(_n ); 00120 } 00121 inline void set_neighbor_discovery_timer( millis_t _t ) 00122 { 00123 neighbor_discovery_timer = _t; 00124 } 00125 inline void set_vicinity_discovery_timer( millis_t _t ) 00126 { 00127 vicinity_discovery_timer = _t; 00128 } 00129 inline Connectivity* get_self( void ) 00130 { 00131 return &self; 00132 } 00133 inline millis_t get_neighbor_discovery_timer( void ) 00134 { 00135 return neighbor_discovery_timer; 00136 } 00137 inline millis_t get_vicinity_discovery_timer( void ) 00138 { 00139 return vicinity_discovery_timer; 00140 } 00141 inline millis_t get_ready_time( void ) 00142 { 00143 return neighbor_discovery_timer + vicinity_discovery_timer + vicinity_filter_timer; 00144 } 00145 inline void set_destination ( const Position& _p ) 00146 { 00147 destination = _p; 00148 } 00149 void destruct() 00150 {} 00151 Radio& radio() 00152 { 00153 return *radio_; 00154 } 00155 Debug& debug() 00156 { 00157 return *debug_; 00158 } 00159 Timer& timer() 00160 { 00161 return *timer_; 00162 } 00163 Rand& rand() 00164 { 00165 return *rand_; 00166 } 00167 private: 00168 00169 Radio* radio_; 00170 Debug* debug_; 00171 Timer* timer_; 00172 Rand* rand_; 00173 enum MessageIds 00174 { 00175 LAZY_NEIGHBOR_DISCOVERY = 31, 00176 LAZY_VICINITY_DISCOVERY = 32, 00177 LAZY_GREEDY_MESSAGE = 33 00178 }; 00179 int callback_id_; 00180 Connectivity self; 00181 ConnectivityList vicinity; 00182 ConnectivityList filtered_vicinity; 00183 millis_t neighbor_discovery_timer; 00184 millis_t vicinity_discovery_timer; 00185 millis_t vicinity_filter_timer; 00186 Position destination; 00187 }; 00188 // ----------------------------------------------------------------------- 00189 template< typename Os_P, 00190 typename Radio_P, 00191 typename Timer_P, 00192 typename Rand_P, 00193 typename Node_P, 00194 typename NodeList_P, 00195 typename Connectivity_P, 00196 typename ConnectivityList_P, 00197 typename Debug_P> 00198 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00199 LazyType() 00200 : callback_id_ ( 0 ) 00201 {} 00202 // ----------------------------------------------------------------------- 00203 template< typename Os_P, 00204 typename Radio_P, 00205 typename Timer_P, 00206 typename Rand_P, 00207 typename Node_P, 00208 typename NodeList_P, 00209 typename Connectivity_P, 00210 typename ConnectivityList_P, 00211 typename Debug_P> 00212 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00213 ~LazyType() 00214 {} 00215 // ----------------------------------------------------------------------- 00216 template< typename Os_P, 00217 typename Radio_P, 00218 typename Timer_P, 00219 typename Rand_P, 00220 typename Node_P, 00221 typename NodeList_P, 00222 typename Connectivity_P, 00223 typename ConnectivityList_P, 00224 typename Debug_P> 00225 void 00226 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00227 enable( void ) 00228 { 00229 radio().enable_radio(); 00230 debug().debug( "Lazy %x: Boot \n", self.get_node().get_id() ); 00231 callback_id_ = radio().template reg_recv_callback<self_type, &self_type::receive>( this ); 00232 millis_t ndt = rand()()%neighbor_discovery_timer; 00233 timer().template set_timer<self_type, &self_type::send_neighbor_discovery>( ndt, this, 0); 00234 millis_t vdt = rand()()%vicinity_discovery_timer; 00235 timer().template set_timer<self_type, &self_type::send_vicinity_discovery>( vdt + neighbor_discovery_timer, this, 0); 00236 vicinity_filter_timer = vicinity_discovery_timer + neighbor_discovery_timer + 2000; 00237 timer().template set_timer<self_type, &self_type::filter_vicinity>( vicinity_filter_timer, this, 0); 00238 //timer().template set_timer<self_type, &self_type::print_neighbors>( vicinity_discovery_timer + neighbor_discovery_timer + 5000, this, 0); 00239 //timer().template set_timer<self_type, &self_type::print_vicinity>( vicinity_discovery_timer + neighbor_discovery_timer + 15000, this, 0); 00240 00241 00242 } 00243 // ----------------------------------------------------------------------- 00244 template< typename Os_P, 00245 typename Radio_P, 00246 typename Timer_P, 00247 typename Rand_P, 00248 typename Node_P, 00249 typename NodeList_P, 00250 typename Connectivity_P, 00251 typename ConnectivityList_P, 00252 typename Debug_P> 00253 void 00254 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00255 disable( void ) 00256 { 00257 debug().debug( "Lazy %x: Disable \n", self.get_node().get_id() ); 00258 radio().unreg_recv_callback( callback_id_ ); 00259 radio().disable(); 00260 } 00261 // ----------------------------------------------------------------------- 00262 template< typename Os_P, 00263 typename Radio_P, 00264 typename Timer_P, 00265 typename Rand_P, 00266 typename Node_P, 00267 typename NodeList_P, 00268 typename Connectivity_P, 00269 typename ConnectivityList_P, 00270 typename Debug_P> 00271 void 00272 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00273 send( node_id_t destination, size_t len, block_data_t *data, message_id_t msg_id ) 00274 { 00275 Message message; 00276 message.set_msg_id( msg_id ); 00277 message.set_payload( len, data ); 00278 radio().send( destination, message.buffer_size(), (uint8_t*)&message ); 00279 } 00280 // ----------------------------------------------------------------------- 00281 template< typename Os_P, 00282 typename Radio_P, 00283 typename Timer_P, 00284 typename Rand_P, 00285 typename Node_P, 00286 typename NodeList_P, 00287 typename Connectivity_P, 00288 typename ConnectivityList_P, 00289 typename Debug_P> 00290 void 00291 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00292 send_neighbor_discovery( void* userdata ) 00293 { 00294 debug().debug( "Lazy %x: Entered Send Neighbor Discovery Message\n", self.get_node().get_id() ); 00295 size_t len = self.get_node().get_buffer_size(); 00296 block_data_t buf[Radio::MAX_MESSAGE_LENGTH]; 00297 block_data_t* buff = buf; 00298 self.get_node().set_buffer_from( buff ); 00299 send( Radio::BROADCAST_ADDRESS, len, (uint8_t*)buff, LAZY_NEIGHBOR_DISCOVERY ); 00300 } 00301 // ----------------------------------------------------------------------- 00302 template< typename Os_P, 00303 typename Radio_P, 00304 typename Timer_P, 00305 typename Rand_P, 00306 typename Node_P, 00307 typename NodeList_P, 00308 typename Connectivity_P, 00309 typename ConnectivityList_P, 00310 typename Debug_P> 00311 void 00312 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00313 send_vicinity_discovery( void* userdata ) 00314 { 00315 debug().debug( "Lazy %x: Entered Send Vicinity Discovery Message\n", self.get_node().get_id() ); 00316 self.print( debug() ); 00317 size_t len = self.get_buffer_size(); 00318 block_data_t buf[Radio::MAX_MESSAGE_LENGTH]; 00319 block_data_t* buff = buf; 00320 self.set_buffer_from( buff ); 00321 send( Radio::BROADCAST_ADDRESS, len, (uint8_t*)buff, LAZY_VICINITY_DISCOVERY ); 00322 } 00323 // ----------------------------------------------------------------------- 00324 template< typename Os_P, 00325 typename Radio_P, 00326 typename Timer_P, 00327 typename Rand_P, 00328 typename Node_P, 00329 typename NodeList_P, 00330 typename Connectivity_P, 00331 typename ConnectivityList_P, 00332 typename Debug_P> 00333 void 00334 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00335 receive( node_id_t from, size_t len, block_data_t *data ) 00336 { 00337 00338 debug().debug( "Lazy %x: Entered Receive\n", self.get_node().get_id() ); 00339 message_id_t msg_id = *data; 00340 Message* message = (Message*)data; 00341 if (msg_id == LAZY_NEIGHBOR_DISCOVERY ) 00342 { 00343 debug().debug( "Lazy %x: Received neighbor discovery message from %x of size %i \n", self.get_node().get_id(), from, len ); 00344 store_neighbor( Node( message->payload() ) ); 00345 } 00346 else if (msg_id == LAZY_VICINITY_DISCOVERY ) 00347 { 00348 debug().debug( "Lazy %x: Received vicinity discovery message from %x of size %i \n", self.get_node().get_id(), from, len ); 00349 store_vicinity( Connectivity( message->payload() ) ); 00350 } 00351 else if (msg_id == LAZY_GREEDY_MESSAGE ) 00352 { 00353 debug().debug( "Lazy %x: Received lazy greedy message from %x of size %i \n", self.get_node().get_id(), from, len ); 00354 Node rec_n = Node( message->payload() ); 00355 if ( decision_lazy( rec_n, from ) ) 00356 { 00357 void* tmp; 00358 send_greedy( tmp ); 00359 } 00360 } 00361 } 00362 // ----------------------------------------------------------------------- 00363 template< typename Os_P, 00364 typename Radio_P, 00365 typename Timer_P, 00366 typename Rand_P, 00367 typename Node_P, 00368 typename NodeList_P, 00369 typename Connectivity_P, 00370 typename ConnectivityList_P, 00371 typename Debug_P> 00372 uint8_t 00373 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00374 decision_lazy( Node n, node_id_t from ) 00375 { 00376 CoordinatesNumber current_distance = n.get_position().distsq( self.get_node().get_position() ); 00377 CoordinatesNumber min_distance = current_distance; 00378 CoordinatesNumber candidate_distance; 00379 node_id_t candidate_id = self.get_node().get_id(); 00380 for ( ConnectivityListIterator i = filtered_vicinity.begin(); i != filtered_vicinity.end(); ++i ) 00381 { 00382 if ( from == i->get_node().get_id() ) 00383 { 00384 for ( NodeListIterator j = ( *i->get_node_list() ).begin(); j != ( *i->get_node_list() ).end(); ++j ) 00385 { 00386 candidate_distance = n.get_position().distsq( j->get_position() ); 00387 if (min_distance >= candidate_distance ) 00388 { 00389 return 0; 00390 } 00391 } 00392 } 00393 } 00394 return 1; 00395 } 00396 // ----------------------------------------------------------------------- 00397 template< typename Os_P, 00398 typename Radio_P, 00399 typename Timer_P, 00400 typename Rand_P, 00401 typename Node_P, 00402 typename NodeList_P, 00403 typename Connectivity_P, 00404 typename ConnectivityList_P, 00405 typename Debug_P> 00406 void 00407 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00408 store_neighbor( Node _n ) 00409 { 00410 NodeListIterator i = ( *self.get_node_list() ).begin(); 00411 while ( i != ( *self.get_node_list() ).end() ) 00412 { 00413 if ( i->get_id() == _n.get_id() ) 00414 { 00415 ( *self.get_node_list() ).erase( i ); 00416 ( *self.get_node_list() ).push_back( _n ); 00417 return; 00418 } 00419 ++i; 00420 } 00421 ( *self.get_node_list() ).push_back( _n ); 00422 } 00423 // ----------------------------------------------------------------------- 00424 template< typename Os_P, 00425 typename Radio_P, 00426 typename Timer_P, 00427 typename Rand_P, 00428 typename Node_P, 00429 typename NodeList_P, 00430 typename Connectivity_P, 00431 typename ConnectivityList_P, 00432 typename Debug_P> 00433 void 00434 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00435 store_vicinity( Connectivity _c ) 00436 { 00437 ConnectivityListIterator i = vicinity.begin(); 00438 while ( i != vicinity.end() ) 00439 { 00440 if ( i->get_node().get_id() == _c.get_node().get_id() ) 00441 { 00442 vicinity.erase( i ); 00443 vicinity.push_back( _c ); 00444 return; 00445 } 00446 ++i; 00447 } 00448 vicinity.push_back( _c ); 00449 } 00450 // ----------------------------------------------------------------------- 00451 template< typename Os_P, 00452 typename Radio_P, 00453 typename Timer_P, 00454 typename Rand_P, 00455 typename Node_P, 00456 typename NodeList_P, 00457 typename Connectivity_P, 00458 typename ConnectivityList_P, 00459 typename Debug_P> 00460 void 00461 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00462 print_neighbors( void* userdata ) 00463 { 00464 self.print( debug() ); 00465 } 00466 // ----------------------------------------------------------------------- 00467 template< typename Os_P, 00468 typename Radio_P, 00469 typename Timer_P, 00470 typename Rand_P, 00471 typename Node_P, 00472 typename NodeList_P, 00473 typename Connectivity_P, 00474 typename ConnectivityList_P, 00475 typename Debug_P> 00476 void 00477 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00478 print_vicinity( void* userdata ) 00479 { 00480 debug().debug( "Lazy %x: Printing filtered vicinity: \n", self.get_node().get_id() ); 00481 for ( ConnectivityListIterator i = filtered_vicinity.begin(); i!=filtered_vicinity.end(); ++i ) 00482 { 00483 i->print( debug() ); 00484 } 00485 } 00486 // ----------------------------------------------------------------------- 00487 template< typename Os_P, 00488 typename Radio_P, 00489 typename Timer_P, 00490 typename Rand_P, 00491 typename Node_P, 00492 typename NodeList_P, 00493 typename Connectivity_P, 00494 typename ConnectivityList_P, 00495 typename Debug_P> 00496 void 00497 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00498 filter_vicinity( void* userdata ) 00499 { 00500 for ( NodeListIterator ni = ( *self.get_node_list() ).begin(); ni != ( *self.get_node_list() ).end(); ++ni ) 00501 { 00502 Connectivity element; 00503 element.set_node( *ni ); 00504 for ( ConnectivityListIterator cli = vicinity.begin(); cli != vicinity.end(); ++cli ) 00505 { 00506 if ( ni->get_id() == cli->get_node().get_id() ) 00507 { 00508 for ( NodeListIterator nli = ( *cli->get_node_list() ).begin(); nli != ( *cli->get_node_list() ).end(); ++nli ) 00509 { 00510 for ( NodeListIterator ni_in = ( *self.get_node_list() ).begin(); ni_in != ( *self.get_node_list() ).end(); ++ni_in ) 00511 { 00512 if ( ni_in->get_id() == nli->get_id() ) 00513 { 00514 ( *element.get_node_list() ).push_back( *nli ); 00515 } 00516 } 00517 } 00518 } 00519 } 00520 filtered_vicinity.push_back( element ); 00521 } 00522 } 00523 // ----------------------------------------------------------------------- 00524 template< typename Os_P, 00525 typename Radio_P, 00526 typename Timer_P, 00527 typename Rand_P, 00528 typename Node_P, 00529 typename NodeList_P, 00530 typename Connectivity_P, 00531 typename ConnectivityList_P, 00532 typename Debug_P> 00533 void 00534 LazyType<Os_P, Radio_P, Timer_P, Rand_P, Node_P, NodeList_P, Connectivity_P, ConnectivityList_P, Debug_P>:: 00535 send_greedy( void* userdata ) 00536 { 00537 debug().debug( "Lazy %x: Entered Send Greedy Message\n", self.get_node().get_id() ); 00538 Node msg_node = Node ( self.get_node().get_id(), destination ); 00539 size_t len = msg_node.get_buffer_size(); 00540 block_data_t buf[Radio::MAX_MESSAGE_LENGTH]; 00541 block_data_t* buff = buf; 00542 msg_node.set_buffer_from( buff ); 00543 send( Radio::BROADCAST_ADDRESS, len, (uint8_t*)buff, LAZY_GREEDY_MESSAGE ); 00544 } 00545 } 00546 #endif
