In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the br...
详细信息
ISBN:
(纸本)9781581134865
In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. Several authors have conjectured that the problem of power-optimal broadcast is NP-complete. We provide here a formal proof, both for the general case and for the geometric one; in the former case, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. We then describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.
In a recent paper, Saad and Schultz discussed several algorithms for broadcasting data in loosely coupled two-dimensional processor grids. This note disputes a claim made about the performance of one of their algorith...
详细信息
In a recent paper, Saad and Schultz discussed several algorithms for broadcasting data in loosely coupled two-dimensional processor grids. This note disputes a claim made about the performance of one of their algorithms. An alternative algorithm is proposed.
作者：
KATSEFF, HPAT&T Bell Labs.
Holmdel NJ USA Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions k-dimensional hypercube has 2k vertices these systems are restricted to having exactly 2k computing nodes. Because system sizes must be a power of two there are large gaps in the sizes of systems that can be b..." property="og:description">
Since a k-dimensional hypercube has 2k vertices, these systems are restricted to having exactly 2k computing nodes. Because system sizes must be a power of two, there are large gaps in the sizes of systems that can be...
详细信息
Since a k-dimensional hypercube has 2k vertices, these systems are restricted to having exactly 2k computing nodes. Because system sizes must be a power of two, there are large gaps in the sizes of systems that can be built with hypercubes. Routing and broadcast algorithms are presented for hypercubes that are missing certain of their nodes, called incomplete hypercubes. Unlike hypercubes, incomplete hypercubes can be used to interconnect systems with any number of processors. The routing and broadcast algorithms for incomplete hypercubes are shown also to be simple and deadlock-free
暂无评论