Radio network Consists of the set of devices that can transmit and receive a message C collIsion uvwx. devices
u v w x collision M M M Radio network u,v,w,x: devices ◼ Consists of the set of devices that can transmit and receive a message
Reachability graph Each node represents a device Each directed edge uv represents that, a node u can transmit to a node y (We say that u is an in-neighbor of v and v is an out-neighbor of Then we can consider a radio network as a directed graph u, v,w: devices
u v w u v w Then we can consider a radio network as a directed graph. • Each node represents a device • Each directed edge uv represents that, a node u can transmit to a node v (We say that u is an in-neighbor of v and v is an out-neighbor of u) u,v,w: devices Reachability graph
Problems Radio broadcasting (rbl Disseminating a message from a source node to all other nodes Acknowledged RB(ArB) Not only rb but also informing a source node of the completion of rb Radio gossiping rg Disseminating messages from each node to all other nodes Acknowledged RG (ARg Not only rb but also informing each node of the completion of RG
Problems Radio Broadcasting (RB) Disseminating a message from a source node to all other nodes Acknowledged RB (ARB) Not only RB but also informing a source node of the completion of RB. Radio Gossiping (RG) Disseminating messages from each node to all other nodes Acknowledged RG (ARG) Not only RB but also informing each node of the completion of RG
Model Each node works per round synchronized by a global clock (like GPS) The initial information of each node ID of itself Whether it is source or not(RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available
Model • Each node works per round synchronized by a global clock (like GPS). • The initial information of each node – ID of itself – Whether it is source or not (RB and ARB) • Each node cannot receive two or more messages in one round • Collision detection is not available
Model Each node works per round synchronized by a global clock (like GPS) The initial information of each node ID of itself Whether it is source or not(RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available Round: Discrete time step of the global clock Actions per round transmission or reception process before and after communication
Round: Discrete time step of the global clock Model Actions per round: • transmission or reception • process before and after communication • Each node works per round synchronized by a global clock (like GPS). • The initial information of each node – ID of itself – Whether it is source or not (RB and ARB) • Each node cannot receive two or more messages in one round • Collision detection is not available