Distributed Assignment of Codes in Multihop Radio Networks

摘要

Code assignment is necessary for the proper functioning of an ad-hoc CDMA network. Due to the irregular topology of ad-hoc networks, an optimal and distributed solution for the code-assignment problem is NP-Complete. This thesis presents a distributed greedy algorithm for assigning codes in a dynamic, multihop wireless CDMA radio network. The same algorithm can be used to assign channels in a multichannel CSMA/CA network. The algorithm does not require any form of synchronization and is completely distributed. It can be used for both the transmitter oriented and receiver oriented code assignment. The algorithm is proven to be correct and its complexity is analyzed. The algorithm has been implemented to assign channels in a multi-channel CSMA/CA network. The results from the implementation are presented here and it is shown that the algorithm is scalable and works correctly in mobile environments.