|
Wiselib
|
wiselib.testing/algorithms/routing/greedy/greedy.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 __GREEDY_H__ 00020 #define __GREEDY_H__ 00021 00022 #include "util/base_classes/routing_base.h" 00023 #include "greedy_message.h" 00024 00025 #include <string.h> 00026 00027 00028 namespace wiselib 00029 { 00039 template<typename OsModel_P, 00040 typename Node_P, 00041 typename NodeList_P, 00042 typename Timer_P = typename OsModel_P::Timer, 00043 typename Radio_P = typename OsModel_P::Radio, 00044 typename Debug_P = typename OsModel_P::Debug> 00045 class Greedy 00046 : public RoutingBase<OsModel_P, Radio_P> 00047 { 00048 public: 00049 typedef OsModel_P OsModel; 00050 typedef Radio_P Radio; 00051 typedef Debug_P Debug; 00052 typedef Node_P Node; 00053 typedef NodeList_P NodeList; 00054 typedef typename Node::NodePosition::Float Float; 00055 typedef Timer_P Timer; 00056 typedef Greedy<OsModel, Node, NodeList, Timer, Radio, Debug> self_type; 00057 typedef typename Radio::node_id_t node_id_t; 00058 typedef typename Radio::size_t size_t; 00059 typedef typename Radio::block_data_t block_data_t; 00060 typedef typename Radio::message_id_t message_id_t; 00061 typedef typename NodeList::iterator NodeList_Iterator; 00062 typedef typename Node::NodePosition Position; 00063 typedef Greedy_Message<OsModel, Node, Radio> Message; 00064 00065 // -------------------------------------------------------------------- 00066 enum SpecialNodeIds { 00067 BROADCAST_ADDRESS = Radio_P::BROADCAST_ADDRESS, 00068 NULL_NODE_ID = Radio_P::NULL_NODE_ID 00069 }; 00070 // -------------------------------------------------------------------- 00071 enum Restrictions { 00072 MAX_MESSAGE_LENGTH = Radio_P::MAX_MESSAGE_LENGTH - Message::PAYLOAD_POS 00073 }; 00074 // -------------------------------------------------------------------- 00075 00076 Greedy( node_id_t sid); 00077 ~Greedy(); 00078 00079 void enable_radio( void ); 00080 void disable_radio( void ); 00081 00082 void send( node_id_t receiver, size_t len, block_data_t *data, message_id_t msg_id, Node n ); 00083 00084 void receive( node_id_t from, size_t len, block_data_t *data ); 00085 00086 void send_neighbor_discovery( void* userdata ); 00087 00088 void send_greedily( void* userdata); 00089 00090 node_id_t greedy_recipient() 00091 { 00092 Node current_greedy_recipient = self; 00093 Node prospective_greedy_recipient; 00094 00095 double current_closest_distance = distsq( destination, current_greedy_recipient.position ); 00096 double prospective_closest_distance; 00097 00098 for ( NodeList_Iterator neighbors_iterator = neighbors.begin(); neighbors_iterator != neighbors.end(); ++neighbors_iterator ) 00099 { 00100 prospective_greedy_recipient = *neighbors_iterator; 00101 prospective_closest_distance = distsq( destination, prospective_greedy_recipient.position ); 00102 00103 if ( prospective_closest_distance < current_closest_distance ) 00104 { 00105 current_closest_distance = prospective_closest_distance; 00106 current_greedy_recipient = prospective_greedy_recipient; 00107 } 00108 } 00109 return current_greedy_recipient.id; 00110 }; 00111 00112 void print_neighbors( void* userdata); 00113 00114 NodeList neighbors; 00115 Node self; 00116 node_id_t sender_id; 00117 Position destination; 00118 00119 void init( Radio& radio, Timer& timer, Debug& debug ) { 00120 radio_ = &radio; 00121 timer_ = &timer; 00122 debug_ = &debug; 00123 } 00124 00125 void destruct() { 00126 } 00127 00128 typename Radio::node_id_t id() 00129 { 00130 return radio_->id(); 00131 }; 00132 00133 private: 00134 Radio& radio() 00135 { return *radio_; } 00136 00137 Timer& timer() 00138 { return *timer_; } 00139 00140 Debug& debug() 00141 { return *debug_; } 00142 00143 Radio * radio_; 00144 Timer * timer_; 00145 Debug * debug_; 00146 00147 00148 enum MessageIds 00149 { 00150 NEIGHBOR_DISCOVERY_MSG_ID, 00151 GREEDY_MSG_ID 00152 }; 00153 00154 int callback_id_; 00155 00156 }; 00157 template<typename OsModel_P, 00158 typename Node_P, 00159 typename NodeList_P, 00160 typename Timer_P, 00161 typename Radio_P, 00162 typename Debug_P> 00163 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00164 Greedy( node_id_t sid) 00165 : callback_id_ ( 0 ) 00166 { 00167 sender_id = sid; 00168 } 00169 // ----------------------------------------------------------------------- 00170 template<typename OsModel_P, 00171 typename Node_P, 00172 typename NodeList_P, 00173 typename Timer_P, 00174 typename Radio_P, 00175 typename Debug_P> 00176 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00177 ~Greedy() 00178 {} 00179 // ----------------------------------------------------------------------- 00180 template<typename OsModel_P, 00181 typename Node_P, 00182 typename NodeList_P, 00183 typename Timer_P, 00184 typename Radio_P, 00185 typename Debug_P> 00186 void 00187 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00188 enable_radio( void ) 00189 { 00190 radio().enable; 00191 self.id = radio().id; 00192 //debug().debug( "Greedy %i: Boot \n", self.id ); 00193 callback_id_ = radio().template reg_recv_callback<self_type, &self_type::receive>( this ); 00194 timer().template set_timer<self_type, &self_type::send_neighbor_discovery>( 10000, this, 0 ); 00195 if ( sender_id == self.id ) 00196 { 00197 timer().template set_timer<self_type, &self_type::send_greedily>( 15000, this, 0 ); 00198 } 00199 } 00200 // ----------------------------------------------------------------------- 00201 template<typename OsModel_P, 00202 typename Node_P, 00203 typename NodeList_P, 00204 typename Timer_P, 00205 typename Radio_P, 00206 typename Debug_P> 00207 void 00208 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00209 disable_radio( void ) 00210 { 00211 //debug().debug( "Greedy %i: Disable \n", self.id ); 00212 radio().unreg_recv_callback( callback_id_ ); 00213 radio().disable; 00214 } 00215 // ----------------------------------------------------------------------- 00216 template<typename OsModel_P, 00217 typename Node_P, 00218 typename NodeList_P, 00219 typename Timer_P, 00220 typename Radio_P, 00221 typename Debug_P> 00222 void 00223 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00224 send( node_id_t destination, size_t len, block_data_t *data, message_id_t msg_id, Node n ) 00225 { 00226 //debug().debug( "Greedy %i : Send \n", self.id ); 00227 Message message; 00228 message.set_msg_id( msg_id ); 00229 message.set_node( n ); 00230 message.set_payload( len, data ); 00231 radio().send( destination, message.buffer_size(), (block_data_t*)&message ); 00232 } 00233 // ----------------------------------------------------------------------- 00234 template<typename OsModel_P, 00235 typename Node_P, 00236 typename NodeList_P, 00237 typename Timer_P, 00238 typename Radio_P, 00239 typename Debug_P> 00240 void 00241 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00242 receive( node_id_t from, size_t len, block_data_t *data ) 00243 { 00244 //debug().debug( "Greedy %i : Receive \n", self.id ); 00245 Message* message = (Message*)data; 00246 if ( message->msg_id() == NEIGHBOR_DISCOVERY_MSG_ID ) 00247 { 00248 NodeList_Iterator neighbors_iterator = neighbors.begin(); 00249 uint8_t found = 0; 00250 while ( neighbors_iterator!=neighbors.end() && found == 0 ) 00251 { 00252 if ( neighbors_iterator->id == message->node().id ) 00253 { 00254 found = 1; 00255 } 00256 if ( found == 0 ){ ++neighbors_iterator; } 00257 } 00258 if ( found == 1 ) 00259 { 00260 neighbors.erase( neighbors_iterator ); 00261 } 00262 neighbors.push_back( message->node() ); 00263 } 00264 else if ( message->msg_id() == GREEDY_MSG_ID ) 00265 { 00266 debug().debug( "Greedy %i : Receive Greedy from %i \n", self.id, from, message->node().position.x , message->node().position.y ); 00267 destination = message->node().position; 00268 send_greedily(NULL); 00269 } 00270 notify_receivers( from, message->payload_size(), message->payload() ); 00271 } 00272 // ----------------------------------------------------------------------- 00273 template<typename OsModel_P, 00274 typename Node_P, 00275 typename NodeList_P, 00276 typename Timer_P, 00277 typename Radio_P, 00278 typename Debug_P> 00279 void 00280 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00281 send_neighbor_discovery( void* userdata) 00282 { 00283 //debug().debug( "Greedy %i : Send neighbor discovery message \n", self.id ); 00284 block_data_t bd[1]; 00285 bd[0] = 'n'; 00286 send( radio().BROADCAST_ADDRESS,1, bd, NEIGHBOR_DISCOVERY_MSG_ID, self ); 00287 } 00288 // ----------------------------------------------------------------------- 00289 template<typename OsModel_P, 00290 typename Node_P, 00291 typename NodeList_P, 00292 typename Timer_P, 00293 typename Radio_P, 00294 typename Debug_P> 00295 void 00296 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00297 send_greedily( void* userdata) 00298 { 00299 node_id_t rec_id = greedy_recipient(); 00300 if (rec_id != self.id) 00301 { 00302 debug().debug( "Greedy %i : Send greedily to %i \n", self.id, rec_id ); 00303 Node dest; 00304 dest.position = destination; 00305 block_data_t bd[1]; 00306 bd[0] = 'g'; 00307 send( greedy_recipient(), 1, bd, GREEDY_MSG_ID, dest ); 00308 } 00309 } 00310 00311 // ----------------------------------------------------------------------- 00312 template<typename OsModel_P, 00313 typename Node_P, 00314 typename NodeList_P, 00315 typename Timer_P, 00316 typename Radio_P, 00317 typename Debug_P> 00318 void 00319 Greedy<OsModel_P, Node_P, NodeList_P, Timer_P, Radio_P, Debug_P>:: 00320 print_neighbors( void* userdata) 00321 { 00322 debug().debug( "Greedy %i : Begin Neighbor printout \n", self.id ); 00323 for ( NodeList_Iterator neighbors_iterator = neighbors.begin(); neighbors_iterator != neighbors.end(); ++neighbors_iterator ) 00324 { 00325 debug().debug( "--- neighbor: id = %i, position = ( %i, %i, %i ) \n", neighbors_iterator->id, neighbors_iterator->position.x, neighbors_iterator->position.y, neighbors_iterator->position.z ); 00326 } 00327 debug().debug( "Greedy %i : End Neighbor printout \n", self.id ); 00328 } 00329 00330 } 00331 #endif
