多盘广播的偏斜索引算法

在移动环境中,多盘广播是被广泛使用的数据广播调度算法之一。为广播数据建立索引可以使移动客户机选择性地监听信道,以减少电源消耗,但过多地插入索引会增加数据访问时间。针对该问题,为多盘广播建立偏斜索引,设计索引树构造算法和广播数据的索引树算法。与可变扇出算法相比,多盘广播的偏斜索引算法需要的平均访问时间和平均调谐时间较短。     

HFC网络中P2P文件共享系统的按需广播算法

为了节省在HFC（Hybrid Fiber Cable）网络中进行P2P（Peer to Peer）文件共享的带宽资源,提高带宽利用率,提出了一种数据广播系统与P2P系统混合的网络拓扑结构,利用广播空闲信道对文件资源索引进行广播。在此拓扑结构基础上,提出了一种按需广播PRLS（Preemptive Request-Length-Serial）算法,提高广播调度的效率。仿真实验表明,在用户平均等待时间和冷、热门索引的数据长度平衡两个指标上,PRLS算法有明显优势。     

非对称网络环境中数据广播的带索引多盘调度算法

在以无线网络为代表的非对称网络环境中,数据广播是一种有效的数据访问方式。针对非均匀的访问概率分布,为了节约移动计算机接听数据广播的电源消耗,同时兼顾访问时间的限制,文中提出了两种带索引多盘调度算法,即复制索引算法（ＩＭＤ－ＲＩ）和多路复用算法（ＩＭＤ－ＭＵＸ）。理论分析和实验结果表明,这两种算法通过在广播信息中加入索引信息,能够有效减少数据广播的调谐时间,同时仍保持较低的访问时间,因此更具有竞争性     

基于重复热点数据的CF广播结构改进算法*

针对现有广播结构构建中对数据访问概率倾斜度考虑不足的问题,在CF索引树的基础上提出了一种基于数据倾斜度的广播构建算法。该算法充分考虑热点数据的请求,根据数据在CF索引树中所处位置的不同,在一个广播周期内重复广播热点数据及其对应的索引节点,尽量减少移动用户的访问时间。最后通过实验验证了改进后广播结构的有效性。     

移动实时环境下一种改进的广播调度算法

在网络带宽不对称的移动实时环境中,数据广播是一种有效的数据访问方式。针对这种网络特性,分析了现今已经存在的某些广播调度算法。针对UFO算法,分别提出了SBS算法和CRS算法,它们从服务器、移动客户端两个方面进行了改进。两种算法可以根据给定的数据项访问概率分布,自动生成广播调度。通过理论分析和实验结果表明,该算法不会产生事务重启,并且可以有效减少数据的访问时间,使用户访问数据广播的平均等待时间最小。     

无线传感网最大剩余能量索引数据分发算法

提出一种基于索引和局部存储的（Index and Local Storage—based,ILS）数据分发算法MREIB—DD。对于ILS类型的数据分发算法,一个事件的监测数据被存储在该数据的监测节点或监测节点的邻居节点。一个存储节点仅当接收到一个来自Sink的查询,才把监测数据发送至Sink。MREIB-DD算法选择网络中有最大剩余能量的节点存储索引信息,传感器节点监测到数据时向索引节点发送该数据的有关索引信息。用户的查询信息先到达索引节点,索引节点把查询转发到数据存储点,存储点对查询进行响应。此算法避免了感知数据的网内传输和查询泛洪带来的开销,分析表明该算法性能优于GHT—DCS算法而复杂度增加较少,是能量高效的数据分发算法。     

基于线性规划的移动数据库广播调度算法研究

阐述了移动计算通用模型和移动数据库广播技术及发展状况,介绍了移动广播领域中经典的多盘广播调度算法。在多盘广播调度算法的基础上,运用统筹学的线性规划对所要广播的数据进行最优规划,并通过调度算法优化调度。     

基于数据访问概率的广播索引技术

在移动计算中,如何节约移动设备的电源是一个重要的研究方向。采用索引广播的方式可以使移动设备选择性地监听信道,从而减少了电源的消耗。该文提出了为广播数据建立基于访问概率的索引技术,并分固定扇出的非平衡索引树和可变扇出的索引树两种情况讨论如何降低平均访问代价。针对这两种情况,分别设计了构造索引树的算法。     

无线传感网最大剩余能量索引数据分发算法

提出一种基于索引和局部存储的(Index and Local Storage-based,ILS)数据分发算法MREIB-DD.对于ILS类型的数据分发算法,一个事件的监测数据被存储在该数据的监测节点或监测节点的邻居节点.一个存储节点仅当接收到一个来自Sink的查询,才把监测数据发送至Sink.MREIB-DD算法选择网络中有最大剩余能量的节点存储索引信息,传感器节点监测到数据时向索引节点发送该数据的有关索引信息.用户的查询信息先到达索引节点,索引节点把查询转发到数据存储点,存储点对查询进行响应.此算法避免了感知数据的网内传输和查询泛洪带来的开销,分析表明该算法性能优于GHT-DCS算法而复杂度增加较少,是能量高效的数据分发算法.     

广播机制解决Shuffle过程数据倾斜的方法

在Spark计算平台中，数据倾斜往往导致某些节点承受更大的网络流量和计算压力，给集群的CPU、内存、磁盘和流量带来了巨大的负担，影响整个集群的计算性能.本文通过对Spark Shuffle设计和算法实现的研究，深入分析在大规模分布式环境下发生数据倾斜的本质原因.提出了广播机制避免Shuffle过程数据倾斜的方法，分析了广播变量分发逻辑过程，给出广播变量性能优势分析和该方法的算法实现.通过Broadcast Join实验验证了该方法在性能上有稳定的提升.     

An efficient nonuniform index in the wireless broadcast environments

Data broadcast is an efficient dissemination method to deliver information to mobile clients through the wireless channel. It allows a huge number of the mobile clients simultaneously access data in the wireless environments. In real-life applications, more popular data may be frequently accessed by clients than less popular ones. Under such scenarios, Acharya et al.’s Broadcast Disks algorithm (BD) allocates more popular data appeared more times in a broadcast period than less popular ones, i.e., the nonuniform broadcast, and provides a good performance on reducing client waiting time. However, mobile devices should constantly tune in to the wireless broadcast channel to examine data, consuming a lot of energy. Using index technologies on the broadcast file can reduce a lot of energy consumption of the mobile devices without significantly increasing client waiting time. In this paper, we propose an efficient nonuniform index called the skewed index, SI, over BD. The proposed algorithm builds an index tree according to skewed access patterns of clients, and allocates index nodes for the popular data more times than those for the less popular ones in a broadcast cycle. From our experimental study, we have shown that our proposed algorithm outperforms the flexible index and the flexible distributed index.     

Exploiting skewed access and energy-efficient algorithm to improve the performance of wireless data broadcasting

As wireless networks become an integral component of the current communication infrastructure, energy efficiency is a crucial design consideration because of the limited battery life of mobile terminals. Data broadcast is an effective data dissemination method in mobile environments. The current air indexing schemes for data broadcast focused on energy efficiency (reducing tuning time) only, and current broadcast scheduling schemes reduce access latency through nonflat data broadcast to improve only responsiveness. Few studies have addressed energy efficiency and responsiveness issues concurrently. This study proposes a fast data access scheme that concurrently supports the energy saving protocol, which constructs broadcast channels according to the access frequency of each type of message to improve energy efficiency in mobile devices. The windmill scheduling algorithm that is presented in this paper was used to organize all types of messages in the broadcast channel in the most symmetrical distribution, to reduce tuning and access time. The performance of the proposed mechanism was analyzed, and the efficiency improvement over existing methods was demonstrated numerically. Results indicate that the proposed mechanism is capable of improving both tuning and access time because of the presence of skewness in the access distribution among disseminated messages.     

Energy-efficient multisite offloading policy using Markov decision process for mobile cloud computing

Mobile systems, such as smartphones, are becoming the primary platform of choice for a user’s computational needs. However, mobile devices still suffer from limited resources such as battery life and processor performance. To address these limitations, a popular approach used in mobile cloud computing is computation offloading, where resource-intensive mobile components are offloaded to more resourceful cloud servers. Prior studies in this area have focused on a form of offloading where only a single server is considered as the offloading site. Because there is now an environment where mobile devices can access multiple cloud providers, it is possible for mobiles to save more energy by offloading energy-intensive components to multiple cloud servers. The method proposed in this paper differentiates the data- and computation-intensive components of an application and performs a multisite offloading in a data and process-centric manner. In this paper, we present a novel model to describe the energy consumption of a multisite application execution and use a discrete time Markov chain (DTMC) to model fading wireless mobile channels. We adopt a Markov decision process (MDP) framework to formulate the multisite partitioning problem as a delay-constrained, least-cost shortest path problem on a state transition graph. Our proposed Energy-efficient Multisite Offloading Policy (EMOP) algorithm, built on a value iteration algorithm (VIA), finds the efficient solution to the multisite partitioning problem. Numerical simulations show that our algorithm considers the different capabilities of sites to distribute appropriate components such that there is a lower energy cost for data transfer from the mobile to the cloud. A multisite offloading execution using our proposed EMOP algorithm achieved a greater reduction on the energy consumption of mobiles when compared to a single site offloading execution.     

一种适用于多任务多资源移动边缘计算环境下的改进粒子群算力卸载算法

为了研究移动设备在多资源复杂环境下的能量消耗问题,提出一种针对移动边缘设备计算卸载的改进粒子群算法。首先基于多环境的移动设备能耗提出一种移动设备能量消耗的计算模型;其次针对计算资源分配问题设计一种可以用于衡量分配方案优劣的适应度算法;最后提出一种改进的粒子群算法,用于求解进一步降低移动边缘设备能耗分配方案的最优解。通过使用模拟仿真软件对多种卸载策略下移动设备能耗、系统响应时间等关键指标对比表明,本文算法在满足用户响应时间的前提下,在求解降低移动设备能耗调度分配方案最优解的过程中具有更优的表现。     

An energy-efficient and access latency optimized indexing scheme for wireless data broadcast

Data broadcast is an attractive data dissemination method in mobile environments. To improve energy efficiency, existing air indexing schemes for data broadcast have focused on reducing tuning time only, i.e., the duration that a mobile client stays active in data accesses. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. This paper proposes an energy-efficient indexing scheme called MHash that optimizes tuning time and access latency in an integrated fashion. MHash reduces tuning time by means of hash-based indexing and enables nonflat data broadcast to reduce access latency. The design of hash function and the optimization of bandwidth allocation are investigated in depth to refine MHash. Experimental results show that, under skewed access distribution, MHash outperforms state-of-the-art air indexing schemes and achieves access latency close to optimal broadcast scheduling.     

Efficient, Energy Conserving Transaction Processing in Wireless Data Broadcast

Broadcasting in wireless mobile computing environments is an effective technique to disseminate information to a massive number of clients equipped with powerful, battery operated devices. To conserve the usage of energy, which is a scarce resource, the information to be broadcast must be organized so that the client can selectively tune in at the desired portion of the broadcast. In this paper, the efficient, energy conserving transaction processing in mobile broadcast environments is examined with widely accepted approaches to indexed data organizations suited for a single item retrieval. The basic idea is to share the index information on multiple data items based on the predeclaration technique. The analytical and simulation studies have been performed to evaluate the effectiveness of our methodology, showing that predeclaration-based transaction processing with selective tuning ability can provide a significant performance improvement of battery life, while retaining a low access time. Tolerance to access failures during transaction processing is also described.     

Effective protocols for kNN search on broadcast multi-dimensional index trees

In a wireless mobile environment, data broadcasting provides an efficient way to disseminate data. Via data broadcasting, a server can provide location-based services to a large client population in a wireless environment. Among different location-based services, the k nearest neighbors (kNN) search is important and is used to find the k closest objects to a given point. However, the kNN search in a broadcast environment is particularly challenging due to the sequential access to the data on a broadcast channel. We propose efficient protocols for the kNN search on a broadcast R-tree, which is a popular multi-dimensional index tree, in a wireless broadcast environment in terms of latency and tuning time as well as memory usage. We investigate how a server schedules the broadcast and provide the corresponding kNN search algorithms at the mobile clients. One of our kNN search protocols further allows a kNN search to start at an arbitrary time instance and it can skip the waiting time for the beginning of a broadcast cycle, thereby reducing the latency. The experimental results validate that our mechanisms achieve the objectives.     

移动环境中自适应的XML广播索引

针对如何减少移动计算环境中XML数据广播的调谐时间和访问时间的问题,提出一种基于自适应索引的XML广播调度算法XAISA。它能根据系统负荷动态调整数据块的度,从而达到性能最优化。性能分析和实验比较表明,该算法能以极小的平均访问时间的代价大大减少平均调谐时间及接收XML广播数据的时间。     

面向边缘设备的高能效深度学习任务调度策略

近年来,深度学习在图像和自然语言处理等诸多领域表现出色,与深度学习相关的各类移动应用发展迅速,但由于移动网络状态的不稳定性及网络带宽的限制,基于云计算的深度模型任务可能出现较大响应延迟,严重影响用户体验.与此同时,深度模型对设备的计算及存储能力有较高的要求,无法直接在资源受限的移动设备中进行部署.因此,亟须设计一种新的计算模式,使得基于深度模型的移动应用能够满足用户对快速响应、低能耗及高准确率的期望.本文提出一种面向边缘设备的深度模型分类任务调度策略,该策略通过协同移动设备与边缘服务器,充分利用智能移动终端的便捷性和边缘服务器强大的计算能力,综合考虑分类任务的复杂度和用户期望,完成深度模型在移动设备和边缘服务器中的动态部署,并对推理任务进行动态调度,从而提升任务执行效率,降低深度学习模型推理开销.本文以基于卷积神经网络的图像识别应用为例,实验结果表明,在移动环境中,相比于准确率最高的深度模型,本文提出的高能效调度策略的推理能耗可降低93.2%、推理时间降低91.6%,同时准确率提升3.88%.