An Information-Theoretic Study On The Establishment And Identification Of Cooperative Relationships Over Multi-Access Channels

With the development of communication networks, the focus of research of information theory has been shifted from point-to-point systems to multi-user networks, and the multi-user information theory has become a hot topic. The traditional multi-user information theory mainly deals with the restoration and transmission of messages in the networks. However, there are many network issues the objectives of which are not transmitting messages, but rather implementing certain tasks through interaction among users,such as distributed computation or coordinating relationship of users. Nevertheless, delivering these tasks does rely on the explicit or implicit communication among users,which is not about the transmission of messages, nor about the complete status of users.Communication for implementing tasks is significantly di?erent from the problem considered in traditional multi-user information theory, and thus, it has attracted considerable attention lately. In this thesis, we have proposed and solved a novel multi-user communication problem aiming at establishing and identifying the relationship of users. Under the circumstance of communication over multi-access Boolean channels, we conduct an information-theoretic study on the bounds of the communication overheads generated during establishing and identifying the users’ relationship. More specifically, our work contains three parts:First, based on the conflict resolution of users who have messages to transmit over the multi-access channels, we formulate a model to study the establishment of the partition relationship among users. Then, we propose a novel framework to reformulate the problem from the view of graph theory, through which the users and their states’ relationship are characterized by a hypergraph. As a result, the partitioning objective can be viewed as a strong coloring of the hypergraph, and the communication can be viewed as a process of removing hyperedges of the hypergraph. In this framework, the e?ect of exchanged information on the establishment of the partition relationship is revealed and quantified. Furthermore, we propose two coding schemes to obtain the achievable bounds of the transmission overhead over an error-free multi-access Boolean channel in the presence of uncertainties caused by collisions. The first one is the brute force method inspired by a source coding perspective, and the second is the random coding approach.By these bounds, it is demonstrated that less communication overheads are needed to partition users, as compared with those for the restoration of users actual states.Second, for the cases of communication over noisy multi-access Boolean channels, we propose a strong typical set based joint edge construction method. By using the random coding approach, we take advantage of the inherent Markov structure of the problem to give an achievable bound of the transmission overhead for establishing the partition relationship. Again, it shows less communication overheads are needed to set up the partition relationship among users, as compared with those for the restoration of users actual states.Third, we formulate a problem to identify the cooperation patterns of users by their proactive communications over multi-access Boolean channels. By expressing the users and their communication relationship through a weighted graph, the problem can be viewed in such a way that users utilize their one-to-one communication to proactively distinguish among a set of weighted graphs known a priori. Based on the stochastic coding method, we first show that the internal connectivity of the graph can be exploited to serve as the identification feature, and then give an explicit solution of the communication overhead under the case with two complementary Paley graphs to di?erentiate. Our proposed approach demonstrates how the graph discrepancy property and the independent set a?ect the solution to the problem.