Search

This paper presents an algorithm for producing near-optimal conflict-free schedules for networks operating under code division multiple access (CDMA). A procedure for finding a lower bound on the length of such schedules is also presented. The presence of both primary and secondary conflicts (due to imperfectly orthogonal CDMA codes) are accounted for by these algorithms. The complexity of both algorithms is analyzed and computational experience with both procedures is presented. Using the lower bound, it is shown that the heuristic is effective. The complexity analysis demonstrates that it is efficient enough to use in networks of realistic size, even when the schedules must be produced in real time.

The Distributed Evolutionary Algorithm (DEA) presented in this paper produces efficient TDMA schedules for communication in an environment of changing network topology by passing topological and traffic information among nodes communicating on the schedule. As information is gained in this way more nodes are added to the communicating group until the entire network is communicating on a common schedule. The key feature of the DEA presented is that the reorganization phase is fast, requiring a number of TDMA slots only on the order of the number of nodes. A secondary feature is that some network communication can take place, and thus some of the traffic requirements can be satisfied, even while the network is being reorganized. Numerical results are presented for a number of randomly generated networks which show how the algorithm performs.