无线多播中基于网络编码的QoS研究

在无线网络中使用网络编码可以提高吞吐量和降低能耗．近来,有许多工作在研究如何利用网络编码来提高吞吐量,但是很少有考虑到QoS．本文重点研究在实时无线网络中数据包在延时约束条件下,网络编码的广播调度问题,目标是在数据包的误时率（deadlinemissratio）容许范围内,减少重传包的数量．我们将综合两种编码调度方案,阐释各自的优劣,动态地选取编码方案．仿真结果显示,我们的算法可以有效减少重传包的数量．     

一种能量均衡的无线传感器网络分簇算法

在无线传感器网络分簇算法的多跳网络模型中,越靠近基站的簇首其转发任务越频繁,从而造成耗能更多,传统分簇算法中对于此问题的考虑较少。在传统算法的周期性更换簇头的思想基础上,进行了改进,一方面动态地对成簇范围进行控制,使越接近基站的区域形成的簇规模越小,减小收集簇内数据的任务,平衡转发任务的能耗。同时引入在簇内选取多个候选簇首的机制来减少簇结构的更换,降低频繁组簇的能耗问题。通过与传统分簇算法的仿真比较证明新算法有效地均衡了网络中节点的能耗,延长了网络生命周期。     

一种改进的智能电网能耗调度算法

为了提高电网的运行效率,提出一种新的实时能耗调度算法,通过考虑负载不确定性来实现每个用户的电费最小化.我们将负载调度描述为一个优化问题.为了降低计算复杂度,提出一种近似动态规划算法,以解决电器运行的调度问题.在研究问题时,考虑了必须运行和可控运行在内的不同电器.与大部分当前需求侧管理算法假设完全知晓用户用电需求不同,算法只需知道将来部分需求的估计即可.仿真结果表明,能量调度算法既降低了用户用电支出,又提高了负载需求的峰均比,为用户和电力公司带来收益.     

一种能量有效的WSN分簇路由算法

针对无线传感器网络(WSN)中的热区问题,提出一种能量有效的WSN分簇路由算法EERA。以基站为圆心将整个感知区域划分为大小不等的圆环,依据节点剩余能量和相对位置选择簇首。簇间采用多跳路由传输数据,路由构建时考虑节点接收和发送数据能耗,将发送距离限制在阈值之内且尽量减少中转次数,簇首节点在稳定传输阶段动态改变转发路径。仿真结果表明,EERA能有效降低网络能耗,均衡网络节点的能耗,延长网络生命周期。     

传感器网络中基于能耗均衡的节点优化部署

在研究无线传感器的问题中,降低网络能量消耗、延长网络寿命是无线传感器网络设计的重要目标,设计中为降低能耗,分簇是实现目标的主要方法。当簇头以单跳通信的方式将数据传输至基站时,远离基站的簇头因传送数据能耗太高而很快死亡。针对矩形监测区域的传感器网络,给出了基于能耗均衡的最大化网络寿命模型,提出了一种非均匀的节点部署算法。通过分析节点的能耗计算出了每层的宽度,并定量规划了每层中需要部署的节点数目。仿真实验表明,非均匀的节点部署算法能有效延长网络的寿命。     

基于移动基站和路由策略WSN寿命的算法

针对无线传感器网络的特点,提出了一种基于移动基站和路由策略优化无线传感器网络寿命的方法.首先给出场景中传感器传输相同信息能耗最小的最佳基站位置,进一步分析了不同基站位置对传感器节点能耗的影响,证明网络中传感器节点传输相同信息的总能耗越小则网络寿命越大.为降低移动基站计算的复杂度以提高采集信息的实时性,应用拉格朗日对偶分解和牛顿法简化均衡节点能量过程中的线性规划问题.当场景中有节点因能量耗尽而无法向基站继续传输信息时,根据场景中的拓扑结构自适应调整基站位置以减少节点的能耗,然后采用简化的线性规划最大最小节点寿命,以提高基站收集信息的有效性.理论分析和仿真研究表明:应用拉格朗日-牛顿法简化线性规划问题能够在保证算法快速收敛的同时大幅度地降低计算量.提出的移动基站策略能够大幅度的延长网络寿命,从而实现增加基站接收信息的数量和提高节点能量使用效率的目的.     

基于权值的非均匀分簇路由算法

节点能量有限是无线传感器网络通信协议设计中的一个重要瓶颈,因此,在无线传感器网络中,考虑网络节点能量的高效利用具有十分重要的理论和实际意义。因而,提出一种基于权值机制的非均匀分簇路由算法,该算法采用权值的局部竞选簇首策略,簇首根据距离信息构建大小不均的多个簇,簇成员节点以链式结构向簇首传送数据,最后簇首采用多跳的方式向基站传送数据。实验仿真结果表明,提出的新算法能有效地降低和均衡网络节点能耗,改善"热区"问题,显著地延长网络生命周期。     

超密集网络中基于多基站博弈均衡的分布式无线资源管理算法

移动边缘计算和超密集网络技术在扩大移动设备计算能力和增加网络容量方面有明显的优势.然而,在两者融合的场景下,如何有效降低基站之间的同信道干扰,减少任务传输的时延和能耗是一个重要研究课题.本文设计了一个基于多基站博弈均衡的分布式无线资源管理算法.将小基站之间的无线资源管理问题转化为博弈问题,提出一种基于奖励驱动的策略选择算法.基站通过迭代不断更新其策略的选择概率,最终优化子信道分配和发射功率的调控.仿真结果表明,我们的算法在提高信道利用率和降低任务处理的时延和能耗方面具有优势.     

一种蜂房移动通信中基于Voronoi图的基站管理方法

蜂房移动通信系统是目前最好的陆地移动通信组网方式。它的正六角形覆盖区域的划分实际上就是以基站为母点，且当母点均匀分布情形下的Voronoi图。然而，传统的计算几何Voronoi图的画法及一些新的适合计算机的画法在实际的应用中还存在一些缺陷，如外围基站边界的确定，在理论上是忽略这个问题的，而实际上必须考虑；基站小区划分也是出于实际考虑而添加的。对传统算法进行了适当的改进，来实现对蜂房移动通信的基站分布信息进行管理。     

面向可信嵌入式系统的随机实时任务能耗优化

针对可信嵌入式系统应用中将任务的最坏情况下的执行时间(WCET)作为任务的实际执行时间,导致系统资源的极大浪费的问题,提出了一种基于随机任务概率模型的方法。首先,考虑任务执行时间具有特定概率分布,并且任务具有不错过其死限的概率(NDVP)需求,同时考虑了动态电压和频率调整(DVFS)对系统可靠性的影响,利用该技术降低能耗。然后,基于动态规划算法,提出了一种具有多项式运行时间的优化算法,并进一步设计了状态剔除规则降低算法运行开销。仿真表明,所提算法与最坏执行时间模型下的最优算法相比,系统能耗降低了30%以上。实验结果表明,考虑任务的随机执行时间能在保证系统可靠性的同时大大节约系统资源。     

An Algorithm for Simultaneous Backbone Threading and Side-Chain Packing

To utilize fully all available information in protein structure prediction, including both backbone and side-chain structures, we present a novel algorithm for solving a generalized threading problem. In this problem we consider simultaneous backbone threading and side-chain packing during the process of a protein structure prediction. For a given query protein sequence and a template structure, our goal is to find a threading alignment between the query sequence and the template structure, along with a rotamer assignment for each side-chain of the query protein, which optimizes an energy function that combines a backbone threading energy and a side-chain packing energy. This highly computationally challenging problem is solved through first formulating this problem as a graph-based optimization problem. Various graph-theoretic techniques are employed to achieve the computational efficiency to make our algorithm practically useful, which takes advantage of a number of special properties of the graph representing this generalized threading problem. The overall framework of our algorithm is a dynamic programming algorithm implemented on an optimal tree decomposition of the graph representation of our problem. By using various additional heuristic techniques such as dead-end elimination, we have demonstrated that our algorithm can solve a generalized threading problem within a practically acceptable amount of time and space, the first of its kind.     

An Algorithm for Simultaneous Backbone Threading and Side-Chain Packing

To fully utilize all available information in protein structure prediction, including both backbone and side-chain structures, we present a novel algorithm for solving a generalized threading problem. In this problem, we consider simultaneously backbone threading and side-chain packing during the process of a protein structure prediction. For a given query protein sequence and a template structure, our goal is to find a threading alignment between the query sequence and the template structure, along with a rotamer assignment for each side-chain of the query protein, which optimizes an energy function that combines a backbone threading energy and a side-chain packing energy. This highly computationally challenging problem is solved through first formulating this problem as a graph-based optimization problem. Various graph-theoretic techniques are employed to achieve the computational efficiency to make our algorithm practically useful, which takes advantage of a number of special properties of the graph representing this generalized threading problem. The overall framework of our algorithm is a dynamic programming algorithm implemented on an optimal tree decomposition of the graph representation of our problem. By using various additional heuristic techniques such as the dead-end elimination, we have demonstrated that our algorithm can solve a generalized threading problem within practically acceptable amount of time and space, the first of its kind.     

Coarse-to-fine dynamic programming

We introduce an extension of dynamic programming, we call "coarse-to-fine dynamic programming" (CFDP), ideally suited to DP problems with large state space. CFDP uses dynamic programming to solve a sequence of coarse approximations which are lower bounds to the original DP problem. These approximations are developed by merging states in the original graph into "superstates" in a coarser graph which uses an optimistic arc cost between superstates. The approximations are designed so that CFDP terminates when the optimal path through the original state graph has been found. CFDP leads to significant decreases in the amount of computation necessary to solve many DP problems and can, in some instances, make otherwise infeasible computations possible. CFDP generalizes to DP problems with continuous state space and we offer a convergence result for this extension. We demonstrate applications of this technique to optimization of functions and boundary estimation in mine recognition     

Test sequencing algorithms with unreliable tests

In this paper, we consider imperfect test sequencing problems under a single fault assumption. This is a partially observed Markov decision problem (POMDP), a sequential multistage decision problem wherein a failure source must be identified using the results of imperfect tests at each stage. The optimal solution for this problem can be obtained by applying a continuous-state dynamic programming (DP) recursion. However, the DP recursion is computationally very expensive owing to the continuous nature of the state vector comprising the probabilities of faults. In order to alleviate this computational explosion, we present an efficient implementation of the DP recursion. We also consider various problems with special structure (parallel systems) and derive closed form solutions/index-rules without having to resort to DP. Finally, we present various top-down graph search algorithms for problems with no special structure, including multistep DP, multistep information heuristics, and certainty equivalence algorithms     

Optimal and approximate approaches for selecting proxy agents in mobile IP based network backbones

In a mobile environment, each mobile host should have a home agent on its home network that maintains a registry of the current location of the mobile host. This registry is normally updated every time a mobile host moves from one subnet to another. We study the tradeoff between the cost of updating the registry and the cost of searching for a mobile host while it is away from home. Using a set of special agents, called proxy agents, which implement a two-tier update process, the cost of updates could be reduced; however, the search cost might increase. We study different approaches to identify a set of proxy agents that minimizes the cost of search. In this paper, we use mathematical programming to obtain optimal solutions to the problem. We consider two situations: the cost of search measured by the sum of all search message costs, and the cost of search measured by the maximum cost of such messages. For these two respective cases we formulate the minimization of the cost of search as Min-Sum and Min-Max problems. For large networks in which the optimization problem may be intractable, we study three different approximate approaches: (1) clustering, (2) genetic algorithms, and (3) simulated annealing. Results of a large set of experiments are presented.     

基于有向图的动态最优航迹规划算法

地形跟随/地形回避(TF/TA)航迹规划是低空突防系统的关键技术之一.通常所使用的动态规划算法得到的规划航迹有时达不到目标点.针对此问题,提出一种最优航迹规划的改进动态规划算法,通过对数字地图进行网格划分并建立有向图的方法改进动态规划算法,使最优航迹能有效地回避障碍和威胁.仿真结果表明,所提出的航迹规划算法是有效的.     

The Sound of Silence: Guessing Games for Saving Energy in a Mobile Environment

This paper explores efficient discrete coding techniques that are motivated by the time–energy trade-off in message transmissions between mobile hosts and mobile support stations. Three algorithms are suggested, two of which use guessing games in which the mobile support station guesses the message to be transmitted by the mobile host and receives an approving signal for a successful guess from the mobile host. The first algorithm is designed to achieve the smallest expected amount of energy while obeying a time bound for message transmissions. The second algorithm achieves the shortest expected transmission time while obeying a bound on the energy. This algorithm uses dynamic programming to construct an optimal tree for the guessing game. Our third algorithm uses a different approach based on the Lempel–Ziv compression algorithm. The time–energy trade-off is controlled by the choice of the length of the codes used to encode strings in the dictionary. The theoretical results obtained are not tied to mobile computing and are of independent interest.     

Easy Cases of Probabilistic Satisfiability

The Probabilistic Satisfiability problem (PSAT) can be considered as a probabilistic counterpart of the classical SAT problem. In a PSAT instance, each clause in a CNF formula is assigned a probability of being true; the problem consists in checking the consistency of the assigned probabilities. Actually, PSAT turns out to be computationally much harder than SAT, e.g., it remains difficult for some classes of formulas where SAT can be solved in polynomial time. A column generation approach has been proposed in the literature, where the pricing sub-problem reduces to a Weighted Max-SAT problem on the original formula. Here we consider some easy cases of PSAT, where it is possible to give a compact representation of the set of consistent probability assignments. We follow two different approaches, based on two different representations of CNF formulas. First we consider a representation based on directed hypergraphs. By extending a well-known integer programming formulation of SAT and Max-SAT, we solve the case in which the hypergraph does not contain cycles; a linear time algorithm is provided for this case. Then we consider the co-occurrence graph associated with a formula. We provide a solution method for the case in which the co-occurrence graph is a partial 2-tree, and we show how to extend this result to partial k-trees with k>2.     

Sub-optimal solutions to track detection problem using graph theoretic concepts

This paper demonstrates how the problem of tracking targets, which appear as either straight or curved lines in two-dimensional display images (or data images) can be formulated in terms of a directed weighted graph model and how dynamic programming techniques can be efficiently applied to reach an optimal or sub-optimal solution. In general, track detection algorithms providing optimal solutions have good detective ability, but most of them suffer from the inability to detect discontinuous lines or to resolve efficiently pairs of crossing lines. A sub-optimal solution is provided that efficiently overcomes these weaknesses. We focus on modeling the track detection problem in terms of a graph, formulating fast sequential/parallel sub-optimal track detection algorithms and testing them on simulated data in order to show their detective ability. Moreover, we specify the conditions under which sub-optimal algorithms can perform at least as well as their corresponding optimal algorithms. This is significant for the track detection problem where fast, accurate and real-time detection is considered a necessity.