Broadcast Networks In Optimization Problems

The optimization of broadcast network is a very important problem in communication networks. Broadcast, namely to transmit the information originally held in one node of the communication network (called Source) to all other nodes. In classical broadcast network, each dissemination of information spend one unite time. There are two kind of communication mode: in shouting mode, the node holding message can transmit the message to all its neighbors once; in whisper mode, the node holding message can communication with at most one neighbor once.Following problems have been studied in this paper. The broadcast in shouting mode in tree is discussed, in which each dissemination of information need not only one unite time but some cost. We provide an algorithm to complete minimum cost broadcast before the given time T0. In non unite time broadcast, we study the non unite time broadcast incomplete graph in whisper mode and in bipartite graph in shouting mode and whisper mode. In linear broadcast, during each unite time any node with message can communication with at most one other node through a path of lines connecting them. We define the cost of each transmission to be the number of edges on the path between the caller and receiver. In this paper, the linear broadcast in train and star graph are studied. Furthermore, reliable broadcast and fault-tolerant broadcast are researched. In reliable broadcast, we put forward a new type fault and study it in product graph. In fault-tolerant broadcast ,we emphasize on the efficient broadcast with linearly bounded faults, namely, at most a i fault in the i th unite time, where 0 < a < 1.