Fixed-parameter algorithms for Kemeny rankings

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permutation” that is “closest” to the given set of permutations. Unfortunately, the problem is NP-hard. We provide a broad study of the parameterized complexity for computing optimal Kemeny rankings. Besides the three obvious parameters “number of votes”, “number of candidates”, and solution size (called Kemeny score), we consider further structural parameterizations. More specifically, we show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall–Tau distance _da$d_a$”. We describe a fixed-parameter algorithm with running time 16^⌈_da⌉⋅poly$16^{\lceil d_a\rceil }\cdot poly$. Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NP-complete in the case of an average range of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP. Finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input.     

Optimal number of annuli for maximizing the lifetime of sensor networks

The most effective way to maximize the lifetime of a wireless sensor network (WSN) is to allocate initial energy to sensors such that they exhaust their energy at the same time. The lifetime of a WSN as well as an optimal initial energy allocation are determined by a network design. The main contribution of the paper is to show that the lifetime of a WSN can be maximized by an optimal network design. We represent the network lifetime as a function of the number m$m$ of annuli and show that m$m$ has significant impact on network lifetime. We prove that if the energy consumed by data transmission is proportional to d^α+c$d^{\alpha }+c$, where d$d$ is the distance of data transmission and α$\alpha$ and c$c$ are some constants, then for a circular area of interest with radius R$R$, the optimal number of annuli that maximizes the network lifetime is m=R((α−1)/c)^1/α$m=R{((\alpha -1)/c)}^{1/\alpha }$ for an arbitrary sensor density function.     

一种小型动/静态双坐标感知系统结构设计

针对提高被动式热释电红外(PIR)传感器的探测距离和范围,提出动/静态双坐标感知系统理论,根据动/静态双坐标感知系统对动态目标实现一定距离内和全范围探测的要求,光学基准传递的要求,提出了小型动/静态双坐标感知系统的结构设计方案。该系统配用红外透镜作为其光学装置,在匀速转台的带动下,实现360°全范围探测红外信号,解决了PIR传感器探测距离和探测视场的矛盾,拓宽了PIR传感器的使用领域。经过实验验证,该系统结构设计合理。     

Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality

Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem   on networks and in continuum domains, and the continuous p$p$-median problem in continuum domains extensively. However, in-depth analysis of the continuous p$p$-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor’s location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p$p$-median problem on a lumped   network and by random sampling. We consider two methods of random sampling: uniform sampling and D²$D^2$-sampling. The first approach with the initial solution of the discrete p$p$-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D²$D^2$-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time.     

Smart sensors

The term Smart Sensors, one of the most strategic devices of Micro System Technologies (MST), refers to sensors which contain both sensing and signal processing capabilities with objectives ranging from simple viewing to sophisticated remote sensing, surveillance, search/track, weapon guidance, robotics, perceptronics and intelligence applications. This paper deals specifically with a new class of smart sensors in infrared spectral bands whose development started some years ago, when it was recognized that the rapid advances of very large scale integration (VLSI) processor technology and mosaic infrared detector array technology could be combined to develop a new generation of infrared smart sensor systems with much improved performances. Sophisticated signal processing operations have been studied for these new systems by integrating microcomputers and other VLSI signal processors within or next to the sensor arrays on the same focal plane, avoiding computing systems located far away from sensors. Recently, this approach has being upgraded by introducing inside the sensor some of the basic function of living eyes, such as dynamic stare, dishomogenity compensation, spatial and temporal filtering. New objectives and requirements and the relevant microsystems technologies are presented for this type of new infrared smart sensors which has been originally developed by us.     

A state-space search approach for optimizing reliability and cost of execution in distributed sensor networks

Sensor networks are increasingly being used for applications which require fast processing of data, such as multimedia processing and collaboration among sensors to relay observed data to a base station (BS). Distributed computing can be used on a sensor network to reduce the completion time of a task (an application) and distribute the energy consumption equitably across all sensors, so that certain sensors do not die out faster than the others. The distribution of task modules to sensors should consider not only the time and energy savings, but must also improve reliability of the entire task execution. We formulate the above as an optimization problem, and use the A^∗$A^{\ast }$ algorithm with improvements to determine an optimal static allocation of modules among a set of sensors. We also suggest a faster algorithm, called the greedy A^∗$A^{\ast }$ algorithm, if a sub-optimal solution is sufficient. Both algorithms have been simulated, and the results have been compared in terms of energy savings, decrease in completion time of the task, and the deviation of the sub-optimal solution from the optimal one. The sub-optimal solution required 8%–35% less computation, at the cost of 2.5%–15% deviation from the optimal solution in terms of average energy spent per sensor node. Both the A^∗$A^{\ast }$ and greedy A^∗$A^{\ast }$ algorithms have been shown to distribute energy consumption more uniformly across sensors than centralized execution. The greedy A^∗$A^{\ast }$ algorithm is found to be scalable, as the number of evaluations in determining the allocation increases linearly with the number of sensors.     

Human–Machine Interaction in Intelligent Robotic Systems: A Unifying Consideration with Implementation Examples

In this paper, we propose a two-layer sensor fusion scheme for multiple hypotheses multisensor systems. To reflect reality in decision making, uncertain decision regions are introduced in the hypotheses testing process. The entire decision space is partitioned into distinct regions of correct, uncertain and incorrect regions. The first layer of decision is made by each sensor indepedently based on a set of optimal decision rules. The fusion process is performed by treating the fusion center as an additional virtual sensor to the system. This virtual sensor makes decision based on the decisions reached by the set of sensors in the system. The optimal decision rules are derived by minimizing the Bayes risk function. As a consequence, the performance of the system as well as individual sensors can be quantified by the probabilities of correct, incorrect and uncertain decisions. Numerical examples of three hypotheses, two and four sensor systems are presented to illustrate the proposed scheme.     

基于热释电红外传感器的车辆和人员分类

设计了一种应用于野外环境中的热释电红外系统,并创新性地提出用单热释电红外传感器节点进行车辆和人员的分类.分类算法利用信号的幅度、信号的持续时间、信号一阶差分值的绝对值的最大值作为特征向量,利用支持向量机（SVM）进行目标分类.在10,20 m处分类准确率分别可以达到93.5％,94.5％,并且针对10,20m的综合分类准确率可以达到92％.该系统扩展了热释电传感器的应用范围和应用场景,所用分类方法对于其他同类传感器系统具有一定的借鉴意义.     

用于WSNs目标探测的传感模块设计

介绍了一种用于无线传感器网络（WSNs）中进行目标探测的传感器模块,描述了它的软硬件设计与数据处理的算法。该设计主要包括传感器单元、微处理器单元和射频通信单元。在传感器单元中对于外界目标的振动、声音和温度传感器信号进行了采集。在微处理器单元中使用数字信号处理对数据进行预处理并取得信号的特征值。在射频通信单元中将特征值通过WSNs传输到上位机。实验证明：该模块具有良好的稳定性和重复性,可以用于多种环境下的目标探测。     

Performance comparison of feature extraction algorithms for target detection and classification

This paper addresses the problem of target detection and classification, where the performance is often limited due to high rates of false alarm and classification error, possibly because of inadequacies in the underlying algorithms of feature extraction from sensory data and subsequent pattern classification. In this paper, a recently reported feature extraction algorithm, symbolic dynamic filtering (SDF), is investigated for target detection and classification by using unmanned ground sensors (UGS). In SDF, sensor time series data are first symbolized to construct probabilistic finite state automata (PFSA) that, in turn, generate low-dimensional feature vectors. In this paper, the performance of SDF is compared with that of two commonly used feature extractors, namely Cepstrum and principal component analysis (PCA), for target detection and classification. Three different pattern classifiers have been employed to compare the performance of the three feature extractors for target detection and human/animal classification by UGS systems based on two sets of field data that consist of passive infrared (PIR) and seismic sensors. The results show consistently superior performance of SDF-based feature extraction over Cepstrum-based and PCA-based feature extraction in terms of successful detection, false alarm, and misclassification rates.     

CoCaMAAL: A cloud-oriented context-aware middleware in ambient assisted living

Research into ambient assisted living (AAL) strives to ease the daily lives of people with disabilities or chronic medical conditions. AAL systems typically consist of multitudes of sensors and embedded devices, generating large amounts of medical and ambient data. However, these biomedical sensors lack the processing power to perform key monitoring and data-aggregation tasks, necessitating data transmission and computation at central locations. The focus here is on the development of a scalable and context-aware framework and easing the flow between data collection and data processing. The resource-constrained nature of typical wearable body sensors is factored into our proposed model, with cloud computing features utilized to provide a real-time assisted-living service. With the myriad of distributed AAL systems at play, each with unique requirements and eccentricities, the challenge lies in the need to service these disparate systems with a middleware layer that is both coherent and flexible. There is significant complexity in the management of sensor data and the derivation of contextual information, as well as in the monitoring of user activities and in locating appropriate situational services. The proposed CoCaMAAL model seeks to address such issues and implement a service-oriented architecture (SOA) for unified context generation. This is done by efficiently aggregating raw sensor data and the timely selection of appropriate services using a context management system (CMS). With a unified model that includes patients, devices, and computational servers in a single virtual community, AAL services are enhanced. We have prototyped the proposed model and implemented some case studies to demonstrate its effectiveness.     

多尺度PCA在传感器故障诊断中的应用研究

A multiscale principal component analysis method is proposed for sensor fault detection and identification. After decomposition of sensor signal by wavelet transform, the coarse-scale coef-ficients from the sensors with strong correlation are employed to establish the principal component analysis model. A moving window is designed to monitor data from each sensor using the model.For the purpose of sensor fault detection and identification, the data in the window is decomposed with wavelet transform to acquire the coarse-scale coefficients firstly, and the square prediction error is used to detect the failure. Then the sensor validity index is introduced to identify faulty sensor,which provides a quantitative identifying index rather than qualitative contrast given by the approach with contribution. Finally, the applicability and effectiveness of the proposed method is illustrated by sensors of industrial boiler.     

Location-centric storage for safety warning based on roadway sensor networks

We propose a novel vision for roadway safety warning based on sensor networks, aiming at providing user-friendly zero-delay safety warnings to motorists. Our idea leverages the advanced sensing, networking and storage technologies. Roadway sensors detect events and store event records at multiple designated locations along the against traffic direction, such that the passing-by drivers can be alerted to potential dangers or traffic delays through the wireless communication between roadway sensors and the vehicle. We design a location-centric storage (LCS) protocol, which manages the propagation and storage of event records based on the time needed to clear the road. In LCS, the density of the sensors storing an event record decreases logarithmically with respect to the distance to the event location. Thus, the closer to the event position, the more number of warnings a driver may obtain. LCS is further tailored for the case of “highway” sensor networks when all sensors are deployed along a straight line mimicking a highway, and the more complex case when two roads intersect at some place. We conduct both theoretic analysis and simulation study to verify the performance of LCS when applied to roadway sensor networks for safety warning. The results indicate that LCS is fair to all sensors. We conclude that roadway safety warning based on sensor networks is a promising idea for realizing ITS's “Zero Fatality, Zero Delay” roadway safety philosophy.