Scheduling sensor activity for information coverage of discrete targets in sensor networks

In this paper, we study the problem of scheduling sensor activity to cover a set of targets with known locations such that all targets can be monitored all the time and the network can operate as long as possible. A solution to this scheduling problem is to partition all sensors into some sensor covers such that each cover can monitor all targets and the covers are activated sequentially. In this paper, we propose to provide information coverage instead of the conventional sensing disk coverage for target. The notion of information coverage is based on estimation theory to exploit the collaborative nature of geographically distributed sensors. Due to the use of information coverage, a target that is not within the sensing disk of any single sensor can still be considered to be monitored (information covered) by the cooperation of more than one sensor. This change of the problem settings complicates the solutions compared to that by using a disk coverage model. We first define the target information coverage (TIC) problem and prove its NP‐completeness. We then propose a heuristic to approximately solve our problem. Simulation results show that our heuristic is better than an existing algorithm and is close to the upper bound when only the sensing disk coverage model is used. Furthermore, simulation results also show that the network lifetime can be significantly improved by using the notion of information coverage compared with that by using the conventional definition of sensing disk coverage. Copyright © 2008 John Wiley & Sons, Ltd.     

Enhanced algorithms for deploying the minimum sensors to construct a wireless sensor network having full coverage of critical square grids

With the rapid technological development of sensors, many applications have been designed to use wireless sensor networks to monitor a certain area and provide quality-of-service guarantees. Therefore, the coverage problem had an important issue for constructing wireless sensor networks. Recently, a coverage problem of constructing a minimum size wireless sensor network to fully cover critical squares in a sensor field, termed CRITICAL-SQUARE-GRID COVERAGE, has received much attention. CRITICAL-SQUARE-GRID COVERAGE is shown to be NP-Complete, and an approximation algorithm, termed Steiner-tree-based critical grid covering algorithm (STBCGCA), is proposed accordingly. In STBCGCA, a sensor is selected to cover critical squares only if at least one of the critical squares is fully covered by the sensor. However, a critical square grid can be cooperatively covered by two or more sensors; that is, one sensor covers one part of the critical square, and the other sensors cover the other part of the critical square. This motivates us to propose two efficient algorithms based on STBCGCA, termed critical-grid-partitioned (CGP-STBCGCA) and reference-point-covered (RPC-STBCGCA), that select sensors that can cooperatively cover critical squares in an attempt to minimize the size of the wireless sensor network. The theoretical analysis shows that sensors deployed by CGP-STBCGCA and RPC-STBCGCA can form a connected wireless sensor network that fully covers all critical grids. In addition, a performance guarantee for CGP-STBCGCA is provided. Simulation results show that the ratio of the average number of deployed sensors in STBCGCA to that in CGP-STBCGCA and RPC-STBCGCA in about 90 % of the cases was between 1.08 and 2.52 for CRITICAL-SQUARE-GRID COVERAGE.     

A Learning Automata-Based Solution to the Priority-Based Target Coverage Problem in Directional Sensor Networks

In recent years, directional sensor networks composed of directional sensors have attracted a great deal of attention due to their extensive applications. The main difficulties associated with directional sensors are their limited battery power and restricted sensing angle. Moreover, each target may have a different coverage quality requirement that can make the problem even more complicated. Therefore, satisfying the coverage quality requirement of all the targets in a specific area and maximizing the network lifetime, known as priority-based target coverage problem, has remained a challenge. As sensors are often densely deployed, organizing the sensor directions into several cover sets and then activating these cover sets successively is a promising solution to this problem. In this paper, we propose a learning automata-based algorithm to organize the directional sensors into several cover sets in such a way that each cover set can satisfy coverage quality requirement of all the targets. In order to verify the performance of the proposed algorithm, several simulations were conducted. The obtained results showed that the proposed algorithm was successful in extending the network lifetime.     

差分进化帝王蝶优化算法求解折扣{0-1}背包问题

帝王蝶优化算法（Monarch Butterfly Optimization,MBO）是一种新颖的群体智能算法,自从提出就在实际优化问题上表现出很好的性能.但是,帝王蝶优化算法的迁移算子采用随机选择两个个体来生成新个体,并没有记忆整个种群的最优解,容易造成全局最优帝王蝶搜索经验的丢失.根据MBO寻优过程的内在机制以及差分进化算法的变异算子能够利用个体间的差异信息,将MBO分别与目前性能最优、应用范围最广的7种差分进化（Differential Evolution,DE）变异策略相结合,实验验证了7种不同算法的性能.基于性能最优的DE/best/2/bin变异模式,提出了一种差分进化帝王蝶优化算法（Monarch Butterfly Optimization Algorithm with Differential Evolution,DEMBO）,使得算法能够记忆种群最优解并实现种群内部信息的充分共享,达到既加快收敛速度又提高解的精度的目的.在30个典型折扣{0-1}背包问题（D{0-1}KP）实例上进行了一系列实验,实验结果表明：（1）DEMBO能够在时间复杂度不变的条件下,显著提高算法的求解精度和收敛速度;（2）DEMBO在求解所有D{0-1}KP实例时,均能够获得一个近似比非常接近1的近似解.     

基于变异算子与模拟退火混合的人工鱼群优化算法

人工鱼群算法(AFSA)是一种新型的群智能随机全局优化技术.本文在分析AFSA存在不足的基础上,提出了基于变异算子与模拟退火混合的人工鱼群优化算法.该算法保持了AFSA算法简单、易实现的特点,克服了人工鱼漫无目的随机游动或在非全局极值点的大量聚集,显著提高了算法的运行效率和求解质量.通过函数和实例测试验证,表明了该算法是可行和有效的.     

自适应混合变异文化算法

只采用单一变异算子的进化规划算法在解决优化问题时,不能兼顾全局探索和局部搜索能力,本文提出柯西+混沌变异和柯西+高斯变异两类混合变异策略,采用文化算法的双层进化机制,提取进化过程中的隐含知识,并根据知识自适应调整两种变异算子的作用时机和作用比例,给出了自适应混合变异文化算法.针对标准测试函数的仿真结果表明,该算法具有更...     

Scheduling algorithms for extending directional sensor network lifetime

Recently, directional sensor networks that are composed of a large number of directional sensors have attracted a great deal of attention. The main issues associated with the directional sensors are limited battery power and restricted sensing angle. Therefore, monitoring all the targets in a given area and, at the same time, maximizing the network lifetime has remained a challenge. As sensors are often densely deployed, a promising approach to conserve the energy of directional sensors is developing efficient scheduling algorithms. These algorithms partition the sensor directions into multiple cover sets each of which is able to monitor all the targets. The problem of constructing the maximum number of cover sets has been modeled as the multiple directional cover sets (MDCS), which has been proved to be an NP-complete problem. In this study, we design two new scheduling algorithms, a greedy-based algorithm and a learning automata (LA)-based algorithm, in order to solve the MDCS problem. In order to evaluate the performance of the proposed algorithms, several experiments were conducted. The obtained results demonstrated the efficiency of both algorithms in terms of extending the network lifetime. Simulation results also revealed that the LA-based algorithm was more successful compared to the greedy-based one in terms of prolonging network lifetime.     

Improving Wireless Sensor Network Lifetime through Power Aware Organization

A critical aspect of applications with wireless sensor networks is network lifetime. Battery-powered sensors are usable as long as they can communicate captured data to a processing node. Sensing and communications consume energy, therefore judicious power management and scheduling can effectively extend operational time. To monitor a set of targets with known locations when ground access in the monitored area is prohibited, one solution is to deploy the sensors remotely, from an aircraft. The loss of precise sensor placement would then be compensated by a large sensor population density in the drop zone, that would improve the probability of target coverage. The data collected from the sensors is sent to a central node for processing. In this paper we propose an efficient method to extend the sensor network operational time by organizing the sensors into a maximal number of disjoint set covers that are activated successively. Only the sensors from the current active set are responsible for monitoring all targets and for transmitting the collected data, while nodes from all other sets are in a low-energy sleep mode. In this paper we address the maximum disjoint set covers problem and we design a heuristic that computes the sets. Theoretical analysis and performance evaluation results are presented to verify our approach.Mihaela Cardei is an Assistant Professor in the Department of Computer Science and Engineering at the Florida Atlantic University. Her research interests are in the areas of wireless networking, wireless sensor networks, algorithm and protocol design in communication networks and resource management. Mihaela Cardei received her M.S. and Ph.D. in Computer Science from the University of Minnesota in 1999 and 2003 respectively. Her Ph.D. adviser was Dr. Ding-Zhu Du. During her graduate studies, she worked with Honeywell Laboratories on the Real Time Adaptive Resource Management DARPA project. She is also a recipient of the University of Minnesota Graduate School Doctoral Dissertation Fellowship for 2002–2003.Ding-Zhu Du received his M.S. degree in 1982 from Institute of Applied Mathematics, Chinese Academy of Sciences under the supervision of Minyi Yue, and his Ph.D. degree in 1985 from the University of California at Santa Barbara under the supervision of Ronald V. Book. He worked at Mathematical Sciences Research Institute, Berkeley in 1985–86, at MIT in 1986–87, and at Princeton University in 1990–91. Currently, he is a professor at Department of Computer Science, University of Minnesota and also a research professor at Institute of Applied Mathematics, Chinese Academy of Sciences. His research interests include combinatorial optimization, communication networks, and theory of computation. He has published more than 140 journal papers and 30 books. Currently, he is the editor-in-chief of Journal of Combinatorial Optimization and book series on Network Theory and Applications. He is also in editorial boards of eight journals.     

Location-unaware coverage in wireless sensor networks

In scenarios where sensors are placed randomly, redundant deployment is essential for ensuring adequate field coverage. This redundancy needs to be efficiently exploited by periodically selecting a subset of nodes (referred to as a “cover”) that actively monitor the field, and putting the remaining nodes to sleep. We consider networks in which sensors are not aware of their locations or the relative directions of their neighbors. We develop several geometric and density-based tests that enable a location-unaware sensor to intelligently determine whether it should turn itself off without degrading the quality of field coverage. These tests rely on distance measurements and exchanged two-hop neighborhood information. We design an algorithm (LUC) that exploits these tests for computing covers. Based on this algorithm, we propose two distributed protocols (LUC-I and LUC-P) that periodically select covers and switch between them so as to extend the network lifetime and tolerate unexpected failures. Our protocols are highly efficient in terms of message overhead and processing complexity. We implement LUC-I in TinyOS and evaluate it using the TOSSIM simulator. Experimental results indicate that our approach significantly prolongs the network lifetime and achieves comparable performance to location-aware protocols.     

自适应混合遗传算法在弹药装载中的应用研究

多约束条件下的弹药装载问题是一个复杂的组合优化问题,属于NP 完全问题,其求解是很困难的。本文在考虑弹药装载中各类约束条件的情况下,对简单遗传算法进行了多方面改进,提出了一种自适应混合遗传算法,来求解弹药装载问题。本文对该算法的编码和解码过程,以及复制算子、交叉算子和变异算子的构建,进行了详细的阐述,给出了使用该算法求解弹药装载问题的具体实现方法。     

Lifetime optimization of wireless sensor networks with sleep mode energy consumption of sensor nodes

The energy constraint is a major issue in wireless sensor networks since battery cells that supply sensor nodes have a limited amount of energy and are neither replaceable nor rechargeable in most cases. A common assumption in previous work is that the energy consumed by sensors in sleep mode is negligible. With this hypothesis, the usual approach is to iteratively consider subsets of nodes that cover all the targets. These subsets, also called cover sets, are then put in the active mode whereas the others are in the low-power or sleep mode. The scheduling of the appropriate cover sets in order to maximize the network lifetime is a challenging problem known to be NP-hard. The consideration of non-zero energy consumption of sensor nodes in sleep mode is more realistic but significantly increases the complexity of the problem. In this paper, we address this question by proposing a greedy algorithm that gives priority to sensors with lowest energy, and uses a blacklist to limit the number of sensors covering critical targets. Simulations show that this algorithm outperforms the previously published solutions. We then propose for regular arrays, an analytical approach which shows that, for any optimal solution, all sensors’ remaining energies are zero. This theoretical approach sheds a new light on ring connected arrays of odd size, that are known to be rather tricky when non-disjoint cover sets are considered.

     

量子概率编码遗传算法及其应用

该文提出了一种基于染色体量子概率编码的遗传算法--QCGA。与传统遗传算法不同,在QCGA中, 单个个体不再表示某一个确定解,而是解的取值概率分布,覆盖整个解空间;各个个体独立并行演化,个体间通过一个新的交叉算子实现演化信息的交换,同时设计了一个新的变异算子以增强算法的局部寻优能力。为了充分考察该算法的有效性和先进性,将其应用于典型函数优化、0-1背包问题和时间序列中频繁结构模式搜索等问题的求解。实验结果表明,与现有同类算法相比,该算法在具有很高搜索效率的同时,仍能维持很高的种群多样性, 因而适用于复杂优化问题的求解。     

基于遗传算法的多传感器数据融合

文章给出了一个新的应用遗传算法技术的分级多传感器数据融合算法，各个传感器信息之间的关系用一种较新的模糊算子确定，与传统的集合论的并、交操作相比，它能更好地模仿人的推理。此外，遗传处法能近似最优地确定模糊算子的参数，使算法在信息源的可靠性，信息的冗余度／互补性以及进行融合的分级结构不确定的情况下，以近似最优的方式对传感器数据进行融合。     

Solving the Redundancy Allocation Problem With a Mix of Components Using the Improved Surrogate Constraint Method

When designing a system, there are two methods that can be used to improve the system's reliability without changing the nature of the system: 1) using more reliable components, and/or 2) providing redundant components within the system. The redundancy allocation problem attempts to find the appropriate mix of components & redundancies within a system in order to either minimize cost subject to a minimum level of reliability, or maximize reliability subject to a maximum cost and weight. Redundancy allocation problems can be classified into two groups; one allows the system to have a mix of components with different characteristics incorporated in the system, while the other only allows one type of each component. The former group has a much larger solution space compared to the latter, and therefore obtaining an exact optimal or even a high quality solution for this problem may be more difficult. Optimization techniques, based on meta-heuristic approaches, have recently been proposed to solve the redundancy allocation problem with a mix of components. However, an exact solution method has not been developed. In this paper, we develop an exact solution method, based on the improved surrogate constraint (ISC) method, and use this method to find optimal solutions to problems previously presented in the literature     

Design of random inspection rate for a flexible assembly system: a heuristic genetic algorithm approach

Because of parts failure in a flexible assembly system (FAS), in-process quality control is necessary. To maximize profit, it is important to derive the inspection rate for each cell. This paper proposes an analytical model using an open queuing network theory for an FAS with feedback and reworking. The problem is solved by a modified genetic algorithm which has two major characteristics. First, the probability of mutation is variable rather than fixed in processing the search. Second, a specified mutation operator with calculating decoded values is proposed according to the status of the solution. These modifications enhance the efficiency and accuracy of the algorithm in empirical experiments.     

On the resolvability of normally distributed vector parameterestimates

This paper presents a metric useful in analyzing the resolution of multidimensional (vector) parameter estimators that produce normal estimates. This metric is based on the distance between ellipsoidal confidence regions about each of the parameters. When the ellipsoids are disjoint the parameters are deemed resolvable. This paper presents a method for finding the noise level at which all of the ellipsoids are disjoint, but at least two are tangent. This is deemed the resolution threshold noise level. The underlying mathematical result treats the problem of finding a dilation (noise level) at which two coupled quadratic equations have a unique solution     

Fast conversion algorithm for very large Boolean functions

Fixed polarity Reed-Muller (FPRM) expressions are alternatives to the traditional sum-of-products forms (SOPs) for the representation of Boolean functions. A fast algorithm is proposed to convert from SOPs to FPRM forms without generating disjoint cube covers or functional decision diagrams (FDDs). This procedure is based on the property of input redundancy and is tailored for very large multiple output Boolean functions. Test results for benchmark examples of up to 199 inputs and 99 outputs are given     

一种新型的自适应混沌遗传算法

针对标准二进制编码遗传算法的缺陷,提出一种基于实数编码技术的新型自适应混沌遗传算法用于求解优化问题.该算法利用信息熵理论产生较好的初始群体分布,并依据概率分布函数构造杂交算子,同时结合混沌动力学特性和人工神经网络理论,设计了一种自适应混沌变异算子,使算法能有效维持群体多样性,防止和克服进化过程中的"早熟"现象,算法操作简单、易于实现.最后通过对几个经典测试函数的数值实验,验证了该算法在提高解的精度和加快收敛速度方面都有显著改善,从而为解决函数优化问题提供了一种行之有效的新方法.     

Routing and wavelength assignment in optical networks from edgedisjoint path algorithms

Routing and wavelength assignment (RWA) problems in wavelength-routed optical networks are typically solved using a combination of integer programming and graph coloring. Such techniques are complex and make extensive use of heuristics. We explore an alternative solution technique in the well-known maximum edge disjoint paths (EDP) problem which can be naturally adapted to the RWA problem. Maximum EDP is NP-hard, but now it is known that simple greedy algorithms for it are as good as any of the more complex heuristic solutions. In this paper we investigate the performance of a simple greedy maximum edge disjoint paths algorithm applied to the RWA problem and compare it with a previously known solution method     

Solving Target Coverage Problem Using Cover Sets in Wireless Sensor Networks Based on Learning Automata

Recent years have witnessed a significant increase in employing wireless sensor networks (WSNs) for a variety of applications. Monitoring a set of discrete targets and, at the same time, extending the network lifetime is a critical issue in WSNs. One method to solve this problem is designing an efficient scheduling algorithm that is able to organize sensor nodes into several cover sets in such a way that each cover set could monitor all the targets. This study presents three learning automata-based scheduling algorithms to solve the problem. Moreover, several pruning rules are devised to avoid the selection of redundant sensors and manage critical sensors for extending the network lifetime. To evaluate the performance of proposed algorithms, we conducted several experiments, and the obtained results indicated that Algorithm 3 was more successful in terms of extending the network lifetime.