Acknowledged Broadcasting and Gossiping in ad hoc radio networks

Lecture 3-3: Networking Architecture, Routing Protocols and Algorithms Acknowledged Broadcasting and Gossiping in ad hoc radio networks Jiro Uchida(nagoya Institute of Technology) Wei Chen tennessee state University) Koichi Wada (nagoya Institute of Technology International Conference on Principles of Distributed Systems, 2003

Acknowledged Broadcasting and Gossiping in ad hoc radio networks Jiro Uchida (Nagoya Institute of Technology) Wei Chen (Tennessee State University) Koichi Wada (Nagoya Institute of Technology) Lecture 3-3: Networking Architecture, Routing Protocols and Algorithms International Conference on Principles of Distributed Systems, 2003

Introduction Ad hoc radio network It provides the flexible communication without base stations and wired networks It is studied as the network in scenarios such as battlefield emergency disaster relief, and so on Various arguments on the broadcasting algorithm in a radio network are presented

Introduction Ad hoc radio network ◼ It provides the flexible communication without base stations and wired networks. ◼ It is studied as the network in scenarios such as battlefield, emergency disaster relief, and so on. ➢ Various arguments on the broadcasting algorithm in a radio network are presented

Radio network Consists of the set of devices that can transmit and receive a message uvwx. devices

Radio network ◼ Consists of the set of devices that can transmit and receive a message. u v w u,v,w,x: devices x

Radio network Consists of the set of devices that can transmit and receive a message uvwx. devices

u v w x Radio network u,v,w,x: devices ◼ Consists of the set of devices that can transmit and receive a message

Radio network Consists of the set of devices that can transmit and receive a message C uvwx. devices

u v w x M M Radio network u,v,w,x: devices ◼ Consists of the set of devices that can transmit and receive a message

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