Distributed computing is an important topic in the field of wireless communications and networking,and its high efficiency in handling large amounts of data is particularly noteworthy.Although distributed computing be...Distributed computing is an important topic in the field of wireless communications and networking,and its high efficiency in handling large amounts of data is particularly noteworthy.Although distributed computing benefits from its ability of processing data in parallel,the communication burden between different servers is incurred,thereby the computation process is detained.Recent researches have applied coding in distributed computing to reduce the communication burden,where repetitive computation is utilized to enable multicast opportunities so that the same coded information can be reused across different servers.To handle the computation tasks in practical heterogeneous systems,we propose a novel coding scheme to effectively mitigate the "straggling effect" in distributed computing.We assume that there are two types of servers in the system and the only difference between them is their computational capabilities,the servers with lower computational capabilities are called stragglers.Given any ratio of fast servers to slow servers and any gap of computational capabilities between them,we achieve approximately the same computation time for both fast and slow servers by assigning different amounts of computation tasks to them,thus reducing the overall computation time.Furthermore,we investigate the informationtheoretic lower bound of the inter-communication load and show that the lower bound is within a constant multiplicative gap to the upper bound achieved by our scheme.Various simulations also validate the effectiveness of the proposed scheme.展开更多
This paper exploits coding to speed up computation offloading in a multi-server mobile edge computing(MEC)network with straggling servers and channel fading.The specific task we consider is to compute the product betw...This paper exploits coding to speed up computation offloading in a multi-server mobile edge computing(MEC)network with straggling servers and channel fading.The specific task we consider is to compute the product between a user-generated input data matrix and a large-scale model matrix that is stored distributively across the multiple edge nodes.The key idea of coding is to introduce computation redundancy to improve robustness against straggling servers and to create communication redundancy to improve reliability against channel fading.We utilize the hybrid design of maximum distance separable(MDS)coding and repetition coding.Based on the hybrid coding scheme,we conduct theoretical analysis on the average task uploading time,average edge computing time,and average output downloading time,respectively and then obtain the end-to-end task execution time.Numerical results demonstrate that when the task uploading phase or the edge computing phase is the performance bottleneck,the hybrid coding reduces to MDS coding;when the downlink transmission is the bottleneck,the hybrid coding reduces to repetition coding.The hybrid coding also outperforms the entangled polynomial coding that causes higher uplink and downlink communication loads.展开更多
The variable block-size motion estimation(ME) and disparity estimation(DE) are adopted in multi-view video coding(MVC) to achieve high coding efficiency. However, much higher computational complexity is also introduce...The variable block-size motion estimation(ME) and disparity estimation(DE) are adopted in multi-view video coding(MVC) to achieve high coding efficiency. However, much higher computational complexity is also introduced in coding system, which hinders practical application of MVC. An efficient fast mode decision method using mode complexity is proposed to reduce the computational complexity. In the proposed method, mode complexity is firstly computed by using the spatial, temporal and inter-view correlation between the current macroblock(MB) and its neighboring MBs. Based on the observation that direct mode is highly possible to be the optimal mode, mode complexity is always checked in advance whether it is below a predefined threshold for providing an efficient early termination opportunity. If this early termination condition is not met, three mode types for the MBs are classified according to the value of mode complexity, i.e., simple mode, medium mode and complex mode, to speed up the encoding process by reducing the number of the variable block modes required to be checked. Furthermore, for simple and medium mode region, the rate distortion(RD) cost of mode 16×16 in the temporal prediction direction is compared with that of the disparity prediction direction, to determine in advance whether the optimal prediction direction is in the temporal prediction direction or not, for skipping unnecessary disparity estimation. Experimental results show that the proposed method is able to significantly reduce the computational load by 78.79% and the total bit rate by 0.07% on average, while only incurring a negligible loss of PSNR(about 0.04 d B on average), compared with the full mode decision(FMD) in the reference software of MVC.展开更多
The growing number of mobile users, as well as the diversification in types of services have resulted in increasing demands for wireless network bandwidth in recent years. Although evolving transmission techniques are...The growing number of mobile users, as well as the diversification in types of services have resulted in increasing demands for wireless network bandwidth in recent years. Although evolving transmission techniques are able to enlarge the network capacity to some degree, they still cannot satisfy the requirements of mobile users. Meanwhile, following Moore's Law, the data processing capabilities of mobile user terminals are continuously improving. In this paper, we explore possible methods of trading strong computational power at wireless terminals for transmission efficiency of communications. Taking the specific scenario of wireless video conversation, we propose a model-based video coding scheme by learning the structures in multimedia contents. Benefiting from both strong computing capability and pre-learned model priors, only low-dimensional parameters need to be transmitted; and the intact multimedia contents can also be reconstructed at the receivers in real-time. Experiment results indicate that, compared to conventional video codecs, the proposed scheme significantly reduces the data rate with the aid of computational capability at wireless terminals.展开更多
In traditional wireless broadcast networks,a corrupted packet must be retransmitted even if it has been lost by only one receiver.Obviously,this is not bandwidth-efficient for the receivers that already hold the retra...In traditional wireless broadcast networks,a corrupted packet must be retransmitted even if it has been lost by only one receiver.Obviously,this is not bandwidth-efficient for the receivers that already hold the retransmitted packet.Therefore,it is important to develop a method to realise efficient broadcast transmission.Network coding is a promising technique in this scenario.However,none of the proposed schemes achieves both high transmission efficiency and low computational complexity simultaneously so far.To address this problem,a novel Efficient Opportunistic Network Coding Retransmission(EONCR)scheme is proposed in this paper.This scheme employs a new packet scheduling algorithm which uses a Packet Distribution Matrix(PDM)directly to select the coded packets.The analysis and simulation results indicate that transmission efficiency of EONCR is over 0.1,more than the schemes proposed previously in some simulation conditions,and the computational overhead is reduced substantially.Hence,it has great application prospects in wireless broadcast networks,especially energyand bandwidth-limited systems such as satellite broadcast systems and Planetary Networks(PNs).展开更多
基金supported by NSF China(No.T2421002,62061146002,62020106005)。
文摘Distributed computing is an important topic in the field of wireless communications and networking,and its high efficiency in handling large amounts of data is particularly noteworthy.Although distributed computing benefits from its ability of processing data in parallel,the communication burden between different servers is incurred,thereby the computation process is detained.Recent researches have applied coding in distributed computing to reduce the communication burden,where repetitive computation is utilized to enable multicast opportunities so that the same coded information can be reused across different servers.To handle the computation tasks in practical heterogeneous systems,we propose a novel coding scheme to effectively mitigate the "straggling effect" in distributed computing.We assume that there are two types of servers in the system and the only difference between them is their computational capabilities,the servers with lower computational capabilities are called stragglers.Given any ratio of fast servers to slow servers and any gap of computational capabilities between them,we achieve approximately the same computation time for both fast and slow servers by assigning different amounts of computation tasks to them,thus reducing the overall computation time.Furthermore,we investigate the informationtheoretic lower bound of the inter-communication load and show that the lower bound is within a constant multiplicative gap to the upper bound achieved by our scheme.Various simulations also validate the effectiveness of the proposed scheme.
基金supported by NSF of China under grant U1908210National Key R&D Project of China under grant 2019YFB1802702。
文摘This paper exploits coding to speed up computation offloading in a multi-server mobile edge computing(MEC)network with straggling servers and channel fading.The specific task we consider is to compute the product between a user-generated input data matrix and a large-scale model matrix that is stored distributively across the multiple edge nodes.The key idea of coding is to introduce computation redundancy to improve robustness against straggling servers and to create communication redundancy to improve reliability against channel fading.We utilize the hybrid design of maximum distance separable(MDS)coding and repetition coding.Based on the hybrid coding scheme,we conduct theoretical analysis on the average task uploading time,average edge computing time,and average output downloading time,respectively and then obtain the end-to-end task execution time.Numerical results demonstrate that when the task uploading phase or the edge computing phase is the performance bottleneck,the hybrid coding reduces to MDS coding;when the downlink transmission is the bottleneck,the hybrid coding reduces to repetition coding.The hybrid coding also outperforms the entangled polynomial coding that causes higher uplink and downlink communication loads.
基金Project(08Y29-7)supported by the Transportation Science and Research Program of Jiangsu Province,ChinaProject(201103051)supported by the Major Infrastructure Program of the Health Monitoring System Hardware Platform Based on Sensor Network Node,China+1 种基金Project(61100111)supported by the National Natural Science Foundation of ChinaProject(BE2011169)supported by the Scientific and Technical Supporting Program of Jiangsu Province,China
文摘The variable block-size motion estimation(ME) and disparity estimation(DE) are adopted in multi-view video coding(MVC) to achieve high coding efficiency. However, much higher computational complexity is also introduced in coding system, which hinders practical application of MVC. An efficient fast mode decision method using mode complexity is proposed to reduce the computational complexity. In the proposed method, mode complexity is firstly computed by using the spatial, temporal and inter-view correlation between the current macroblock(MB) and its neighboring MBs. Based on the observation that direct mode is highly possible to be the optimal mode, mode complexity is always checked in advance whether it is below a predefined threshold for providing an efficient early termination opportunity. If this early termination condition is not met, three mode types for the MBs are classified according to the value of mode complexity, i.e., simple mode, medium mode and complex mode, to speed up the encoding process by reducing the number of the variable block modes required to be checked. Furthermore, for simple and medium mode region, the rate distortion(RD) cost of mode 16×16 in the temporal prediction direction is compared with that of the disparity prediction direction, to determine in advance whether the optimal prediction direction is in the temporal prediction direction or not, for skipping unnecessary disparity estimation. Experimental results show that the proposed method is able to significantly reduce the computational load by 78.79% and the total bit rate by 0.07% on average, while only incurring a negligible loss of PSNR(about 0.04 d B on average), compared with the full mode decision(FMD) in the reference software of MVC.
基金supported by the National Basic Research Project of China (973) (2013CB329006)National Natural Science Foundation of China (NSFC, 61101071,61471220, 61021001)Tsinghua University Initiative Scientific Research Program
文摘The growing number of mobile users, as well as the diversification in types of services have resulted in increasing demands for wireless network bandwidth in recent years. Although evolving transmission techniques are able to enlarge the network capacity to some degree, they still cannot satisfy the requirements of mobile users. Meanwhile, following Moore's Law, the data processing capabilities of mobile user terminals are continuously improving. In this paper, we explore possible methods of trading strong computational power at wireless terminals for transmission efficiency of communications. Taking the specific scenario of wireless video conversation, we propose a model-based video coding scheme by learning the structures in multimedia contents. Benefiting from both strong computing capability and pre-learned model priors, only low-dimensional parameters need to be transmitted; and the intact multimedia contents can also be reconstructed at the receivers in real-time. Experiment results indicate that, compared to conventional video codecs, the proposed scheme significantly reduces the data rate with the aid of computational capability at wireless terminals.
基金supported in part by the National Natural Science Foundation of China under Grant No. 61032004the National High Technical Research and Development Program of China (863 Program) under Grants No. 2012AA121605,No. 2012AA01A503,No.2012AA01A510
文摘In traditional wireless broadcast networks,a corrupted packet must be retransmitted even if it has been lost by only one receiver.Obviously,this is not bandwidth-efficient for the receivers that already hold the retransmitted packet.Therefore,it is important to develop a method to realise efficient broadcast transmission.Network coding is a promising technique in this scenario.However,none of the proposed schemes achieves both high transmission efficiency and low computational complexity simultaneously so far.To address this problem,a novel Efficient Opportunistic Network Coding Retransmission(EONCR)scheme is proposed in this paper.This scheme employs a new packet scheduling algorithm which uses a Packet Distribution Matrix(PDM)directly to select the coded packets.The analysis and simulation results indicate that transmission efficiency of EONCR is over 0.1,more than the schemes proposed previously in some simulation conditions,and the computational overhead is reduced substantially.Hence,it has great application prospects in wireless broadcast networks,especially energyand bandwidth-limited systems such as satellite broadcast systems and Planetary Networks(PNs).
