| Future wireless networks are expected to interconnect trillions of products,machines,and devices.To serve such an enormous number of nodes and achieve a massive number of interconnections,the shuffle and aggregation of a large amount of distributed data can not be avoided.However,with the limited radio frequency resources,it is impractical to aggregate data using conventional orthogonal multi-access schemes since this would result in excessive network latency and low spectrum utilization efficiency.Recent advances show that an emerging method,called computation over multi-access channels(CoMAC),utilizes the signal-superposition property of wireless channels to compute a desired function over the air without collecting the corresponding individual data.This would significantly improve the latency of the operation of network functions.For instance,wireless sensor networks always focus on a function(e.g.,arithmetic mean,variance,and median)of the sensor readings(e.g.,temperature,humidity,and atmospheric pressure)within the served area.Also,wireless distributed computing networks wish to obtain the results of the objective task.This implies that CoMAC is a promising technology for the networks only interested in the desired functions of the individual data from distributed nodes.This dissertation focuses on the network design and the resource allocation of Co-MAC regarding three different kinds of wireless networks.The first one is for the most common wide-band wireless networks.Considering the frequency-selective channel of wide-band systems,this dissertation proposes the design of the function-division-based wide-band CoMAC to leverage the flexibility of sub-carriers.Secondly,this dissertation proposes a multi-layer function-computation method for multi-hop(multi-relay)networks with long-distance transmission.This method can not only protect the original topology but also efficiently compute functions.Since nodes may have disparate capabilities in practice,in the end,this dissertation investigates the heterogeneous wireless networks where nodes own different capabilities to compute tasks and transmit results.It shows that some slow nodes(i.e.,stragglers)may cause performance loss in such networks.To deal with the stragglers,the wireless coded computation is applied in Co-MAC,which uses the idea of coding theory.Specifically,the main contribution of this dissertation is given in the following three parts.(1)For the wide-band networks,we propose the use of orthogonal frequency division multiplexing in wide-band CoMAC to transmit functions in a similar way to bit sequences through division,allocation,and reconstruction of functions.A general achievable rate is derived and we formulate an optimization problem considering power allocation.A sponge-squeezing algorithm adapted from the classical water-filling algorithm is proposed to solve the optimal power allocation problem.The improved computation rate of the proposed framework and the corresponding allocation has been verified through both theoretical analysis and numerical results.Furthermore,we use the idea of non-orthogonal multiple access(NOMA)and propose the sub-function superposi-tion where multiple sub-functions are selected to be superposed over each sub-carrier.The corresponding achievable rate is derived based on sub-function superposition.We further study the limiting case when the number of nodes goes to infinity.An exact expression of the rate is derived that provides a lower bound on the computation rate.Com-pared with the existing CoMAC,the NOMA-based CoMAC achieves a higher computation rate.Furthermore,the diversity order of the computation rate is derived,which shows that the system performance is dominated by the node with the worst channel gain among these sub-functions in each sub-carrier.(2)As for multi-hop networks,we propose multi-layer CoMAC by combining Co-MAC and orthogonal communication to compute functions in the multi-hop network.Firstly,to make the multi-hop network more tractable,we reorganize it into a hierarchical network with multiple layers that consists of subgroups and groups.Then,in the hierarchical network,the implementation of multi-layer CoMAC is given by comput-ing and communicating subgroup and group functions over layers,where CoMAC is applied to compute each subgroup function and orthogonal communication is adopted for each group to obtain the group function.The general computation rate is derived and the performance is further improved through time allocation and power control.The closed-form solutions to optimization problems are obtained,which suggests that orthogonal communication and existing CoMAC schemes are generalized.(3)For heterogeneous networks where nodes have different transmission rates and different computation capabilities,we find that the computation stragglers and transmis-sion stragglers heavily influence the performance.To deal with both stragglers,wireless coded computation is proposed for CoMAC systems of wireless distributed computing networks,where the addition of redundant computing tasks and the selection of suitable nodes are used to reduce overall latency.Furthermore,to take advantage of the abandoned nodes,each node divides the local data block into several sub-blocks,i.e.,the desired computation task is divided into several sub-tasks.In this case,we choose the optimal encoding strategy for each sub-task so that the overall latency of computation and transmission can be further improved.Then,the derived overall latency shows that existing works are generalized and there exists a trade-off between computation and transmission concerning the number of the divided sub-blocks.To achieve the optimal trade-off,we formulate optimization problems and obtain the(sub)optimal solutions,which are verified through simulation results. |
PDF Full Text Request