Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree

In some applications, wireless sensor networks (WSNs) operate in very harsh environments and nodes become subject to increased risk of damage. Sometimes a WSN suffers from the simultaneous failure of multiple sensors and gets partitioned into disjoint segments. Restoring network connectivity in such a case is crucial in order to avoid negative effects on the application. Given that WSNs often operate unattended in remote areas, the recovery should be autonomous. This paper promotes an effective strategy for restoring the connectivity among these segments by populating the least number of relay nodes. Finding the optimal count and position of relay nodes is NP-hard and heuristics are thus pursued. We propose a Distributed algorithm for Optimized Relay node placement using Minimum Steiner tree (DORMS). Since in autonomously operating WSNs it is infeasible to perform a network-wide analysis to diagnose where segments are located, DORMS moves relay nodes from each segment toward the center of the deployment area. As soon as those relays become in range of each other, the partitioned segments resume operation. DORMS further model such initial inter-segment topology as Steiner tree in order to minimize the count of required relays. Disengaged relays can return to their respective segments to resume their pre-failure duties. We analyze DORMS mathematically and explain the beneficial aspects of the resulting topology with respect to connectivity, and traffic balance. The performance of DORMS is validated through extensive simulation experiments.     

Design of steady-state minimum variance controllers

A new technique to design optimal controllers is presented for plants described by rational transfer functions and additive disturbances with rational spectral densities. The objective is to minimize a weighted sum of the plant input and output steady-state variances subject to asymptotic stability of the closed-loop system.The technique is based on polynomial algebra. In fact, the design procedure is reduced to solving two linear polynomial equations whose unique solution directly yields the optimal controller transfer function as well as the minimized cost. This approach is simple, computationally attractive, and can handle unstable and/or nonminimum-phase plants with improper transfer functions.An integral part of the paper are effective computational algorithms, which include the spectral factorization, the solution of polynomial equations, and the evaluation of minimum cost.     

Methods of steady-state simulation for gas networks

Relationships between different methods of steady-state simulation for gas networks have been analysed. This analysis has been carried out on the assumption that the problem of simulation is solved by the multidimensional Newton method. By varying the assumptions made concerning the set of basic equations (Kirchhoff's first and second laws and the flow equation), four different formulations have been obtained, i.e. the loop method, the loop-node method, the node method and the node-loop method. The advantages and disadvantages of each formulation are described.     

A rounding algorithm for approximating minimum Manhattan networks

For a set T$T$ of n$n$ points (terminals) in the plane, a Manhattan network   on T$T$ is a network N(T)=(V,E)$N\left(T\right)=(V,E)$ with the property that its edges are horizontal or vertical segments connecting points in V⊇T$V\supseteq T$ and for every pair of terminals, the network N(T)$N\left(T\right)$ contains a shortest _l1$l_1$-path between them. A minimum Manhattan network   on T$T$ is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan [J. Gudmundsson, C. Levcopoulos, G. Narasimhan, Approximating a minimum Manhattan network, Nordic Journal of Computing 8 (2001) 219–232. Proc. APPROX’99, 1999, pp. 28–37] and its complexity status is unknown. Several approximation algorithms (with factors 8, 4, and 3) have been proposed; recently Kato, Imai, and Asano [R. Kato, K. Imai, T. Asano, An improved algorithm for the minimum Manhattan network problem, ISAAC’02, in: LNCS, vol. 2518, 2002, pp. 344–356] have given a factor 2-approximation algorithm, however their correctness proof is incomplete. In this paper, we propose a rounding 2-approximation algorithm based on an LP-formulation of the minimum Manhattan network problem.     

An online activation moments determination for steady-state optimization

A method for an activation moments determination of steady-state optimizing control is developed for systems subject to disturbance inputs. This method is based on the deviation between the performance index of the controlled process and its optimal value. The estimate of the deviation is online, carried out based on the approximation of the performance index optimal value, which is a function of the disturbance inputs. It is assumed that the disturbance inputs as a representation of disturbances are available on the basis of measure and predication. The system implemented proposed method cooperates in the natural way with the scheduling algorithm of the control computer. A practical utility of the proposed approach has been presented by application to the control of a simulated stirred-tank reactor. The proposed method for the activation moments determination has been compared with the periodical activation method.     

Trust-based minimum cost opportunistic routing for Ad hoc networks

Recently, opportunistic routing has received much attention as a new design direction. It can exploit the wireless broadcast and more highly reliable opportunistic forwarding, so as to substantially increase the throughput of network. Due to dynamic topology, distributed collaboration, limited bandwidth and computing ability, the absence of enough physical protection in Ad hoc networks, opportunistic routing is vulnerable to attacks by malicious nodes. In order to alleviate the malicious behaviors, we incorporate the concept of trust to Ad hoc networks, build a simple trust model to evaluate neighbors’ forwarding behavior and apply this model to opportunistic routing for Ad hoc networks. A new trusted opportunistic forwarding model is proposed by choosing the trusted and highest priority candidate forwarder, then a trusted minimum cost routing algorithm (MCOR) is formally formulated, the correctness and effectiveness of this algorithm from theoretical analysis are also approved. Finally, MCOR algorithm is verified by simulation using nsclick software and compared its performance with the classic protocols: ExOR, TAODV and Watchdog-DSR. The simulation results show that MCOR scheme can detect and mitigate node misbehaviors. Furthermore, MCOR scheme outperforms the other protocols in terms of: throughput, delay, Expected ETX, security-gains and cost of routing.     

An integrated system for designing minimum cost survivabletelecommunications networks

This paper provides a Design System for obtaining minimum cost survivable telecommunications networks. It integrates heuristics for obtaining survivable topologies and improving the cost of the network with heuristics for provisioning capacity. The heuristics are based on the characteristic of the underlying graph. The Design System provides survivable telecommunications networks with 25 nodes in a matter of seconds and within 16% of a fairly relaxed lower bound     

Recurrent neural networks for minimum infinity-norm kinematiccontrol of redundant manipulators

This paper presents two neural network approaches to minimum infinity-norm solution of the velocity inverse kinematics problem for redundant robots. Three recurrent neural networks are applied for determining a joint velocity vector with its maximum absolute value component being minimal among all possible joint velocity vectors corresponding to the desired end-effector velocity. In each proposed neural network approach, two cooperating recurrent neural networks are used. The first approach employs two Tank-Hopfield networks for linear programming. The second approach employs two two-layer recurrent neural networks for quadratic programming and linear programming, respectively. Both the minimal 2-norm and infinity-norm of joint velocity vector can be obtained from the output of the recurrent neural networks. Simulation results demonstrate that the proposed approaches are effective with the second approach being better in terms of accuracy and optimality     

A parametric method for computing the steady-state characteristics of electric power-supply systems

Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 140–146, January–February, 1994.     

Multi-rate distributed fusion estimation for sensor networks with packet losses

This paper presents a distributed fusion estimation method for estimating states of a dynamical process observed by wireless sensor networks (WSNs) with random packet losses. It is assumed that the dynamical process is not changing too rapidly, and a multi-rate scheme by which the sensors estimate states at a faster time scale and exchange information with neighbors at a slower time scale is proposed to reduce communication costs. The estimation is performed by taking into account the random packet losses in two stages. At the first stage, every sensor in the WSN collects measurements from its neighbors to generate a local estimate, then local estimates in the neighbors are further collected at the second stage to form a fused estimate to improve estimation performance and reduce disagreements among local estimates at different sensors. Local optimal linear estimators are designed by using the orthogonal projection principle, and the fusion estimators are designed by using a fusion rule weighted by matrices in the linear minimum variance sense. Simulations of a target tracking system are given to show that the time scale of information exchange among sensors can be slower while still maintaining satisfactory estimation performance by using the developed estimation method.     

Approximating minimum independent dominating sets in wireless networks

We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property.     

一种改进的无线传感器网络最小跳数路由协议

针对无线传感器网络最小跳数路由协议数据包多路径冗余传输,能量消耗不均衡等问题,提出了一种改进的无线传感器网络最小跳数路由协议。该协议通过引入侦听机制在网络中建立传输路径,同时采用一种新的能量均衡策略解决关键节点能耗过快的问题,以有效延长网络寿命。通过自主研发的无线传感器网络仿真平台进行仿真,比较最小跳数路由协议和改进协议的性能。实验结果表明:改进协议能够很好的均衡网络能量消耗,提高网络能量有效性,延长了网络寿命。     

Exact algorithms for the minimum power symmetric connectivity problem in wireless networks

In this paper we consider the problem of assigning transmission powers to the nodes of a wireless network in such a way that all the nodes are connected by bidirectional links and the total power consumption is minimized.Two mixed integer programming formulations are presented together with some new valid inequalities for the polytopes associated. A preprocessing technique and two exact algorithms based on the formulations previously introduced are also proposed.Comprehensive computational results, which show the effectiveness of the new valid inequalities and of the preprocessing technique are presented. The experiments also show that the exact approaches we propose outperform more complex methods recently appeared in the literature.     

Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks

Motivated by cooperative communication in ad hoc networks, Wu et al. proposed extended dominating set (EDS) where each node in an ad hoc network is covered by either a dominating neighbor or several 2-hop dominating neighbors, and defined two types of dominating sets: extended strongly connected dominating set (ECDS) and extended weakly connected dominating set (EWCDS), according to the success of a broadcast process. An EWCDS is an effective method for clustering. In this paper, we extend the dominative capabilities of nodes such that each forward node dominates not only itself and its regular neighbors fully, but also its quasi-neighbors partly. Based on this extension, three novel algorithms to find EWCDSs in ad hoc networks are proposed. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations.     

无线传感器网络最少数量通信节点定位方法

随机布置的无线传感器网络,通信节点数量和位置影响网络性能。利用免疫理论与矢量量化技术提出了一种具有最少数量特性的无线传感器网络通信节点定位方法。根据生物免疫机制建立无线传感器节点激活模型,基于免疫自适应调节算法确定传递事件信息所需最少通信节点数;以全部节点坐标为矢量,通信节点数为矢量类别,矢量量化后获得的代表矢量即为通信节点在监测区域的位置。仿真结果表明该方法能极大地减少通信节点数量,优化网络空间资源布局。     

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。     

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是：首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。     

A decision model for reducing active power losses during electric power dispatching

This paper focuses on the issue of power dispatching. In order to reduce fuel loss and fuel expenditure during power dispatching, a nonlinear mathematical model is proposed in this research. Slightly different versions of this model are used to calculate a steady-state regime, to minimize active power losses during the power despatch process, and to calculate some contingency regimes for emergency cases. An expert system that integrates the optimization methods and artificial intelligence (AI) techniques has been developed and implemented in a subsystem of the Romanian Power System.     

Artificial electric field algorithm with inertia and repulsion for spherical minimum spanning tree

Applied Intelligence - Artificial electric field algorithm (AEFA) is a potential global optimization algorithm proposed in recent years and has been successfully applied to various engineering...