Representation and solutions for simultaneous transmissions over broadcast medium

摘要

Embodiments of a system and method for finding optimal routes for simultaneous transmissions over broadcast medium are generally described herein. In some embodiments, nodes are placed into a cost matrix representing a connected graph of nodes, virtual nodes are identified by applying matrix operations to the cost matrix and backtracking is performed incrementally to build candidates of virtual nodes for a solution set from the identified virtual nodes and to eliminate unsuitable candidates.

主权项

1. A method for finding optimal routes for multicast transmissions over broadcast media to a destination set of nodes, the method comprising:
placing nodes into a cost matrix representing a connected graph of nodes; identifying virtual nodes by applying matrix operations to the cost matrix, each of the virtual nodes being defined as a combination of nodes reachable via a single multicast transmission from a corresponding source node, wherein each of the virtual nodes has a link cost equal to a maximum link cost from among its combination of nodes; and executing an incremental backtracking procedure to build a solution set of candidate routes including virtual nodes, virtual nodes that are subsets of virtual nodes, and actual nodes to carry multicast transmissions to the destination set of nodes; and selecting an optimal set of routes from among the candidate routes that have a combined lowest overall link cost to the destination set of nodes.