Efficient distributed data scheduling algorithm for data aggregation in wireless sensor networks

With the rapid development of applications for wireless sensor networks, efficient data aggregation methods are becoming increasingly emphasized. Many researchers have studied the problem of reporting data with minimum energy cost when data is allowed to be aggregated many times. However, some aggregation functions used to aggregate multiple data into one packet are unrepeatable; that is, every data is aggregated only at most once. This problem motivated us to study reporting data with minimum energy cost subject to that a fixed number of data are allowed to be aggregated into one packet and every data is aggregated at most once. In this paper, we propose novel data aggregation and routing structures for reporting generated data. With the structures, we study the problem of scheduling data to nodes in the networks for data aggregation such that the energy cost of reporting data is minimized, termed MINIMUM ENERGY-COST DATA-AGGREGATION SCHEDULING. In addition, we show that MINIMUM ENERGY-COST DATA-AGGREGATION SCHEDULING is NP-complete. Furthermore, a distributed data scheduling algorithm is proposed accordingly. Simulations show that the proposed algorithm provides a good solution for MINIMUM ENERGY-COST DATA-AGGREGATION SCHEDULING.     

A simple, least-time, and energy-efficient routing protocol with one-level data aggregation for wireless sensor networks

The area of wireless sensor networks (WSN) is currently attractive in the research community area due to its applications in diverse fields such as defense security, civilian applications and medical research. Routing is a serious issue in WSN due to the use of computationally-constrained and resource-constrained micro-sensors. These constraints prohibit the deployment of traditional routing protocols designed for other ad hoc wireless networks. Any routing protocol designed for use in WSN should be reliable, energy-efficient and should increase the lifetime of the network. We propose a simple, least-time, energy-efficient routing protocol with one-level data aggregation that ensures increased life time for the network. The proposed protocol was compared with popular ad hoc and sensor network routing protocols, viz., AODV ( [35] and [12]), DSR (Johnson et al., 2001), DSDV (Perkins and Bhagwat, 1994), DD (Intanagonwiwat et al., 2000) and MCF (Ye et al., 2001). It was observed that the proposed protocol outperformed them in throughput, latency, average energy consumption and average network lifetime. The proposed protocol uses absolute time and node energy as the criteria for routing, this ensures reliability and congestion avoidance.     

Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks

This paper investigates the design of fault-tolerant TDMA-based data aggregation scheduling (DAS) protocols for wireless sensor networks (WSNs). DAS is a fundamental pattern of communication in wireless sensor networks where sensor nodes aggregate and relay data to a sink node. However, any such DAS protocol needs to be cognisant of the fact that crash failures can occur. We make the following contributions: (i) we identify a necessary condition to solve the DAS problem, (ii) we introduce a strong and weak version of the DAS problem, (iii) we show several impossibility results due to the crash failures, (iv) we develop a modular local algorithm that solves stabilising weak DAS and (v) we show, through simulations and an actual deployment on a small testbed, how specific instantiations of parameters can lead to the algorithm achieving very efficient stabilisation.     

An adaptive in-network aggregation operator for query processing in wireless sensor networks

A wireless sensor network (WSN) is composed of tens or hundreds of spatially distributed autonomous nodes, called sensors. Sensors are devices used to collect data from the environment related to the detection or measurement of physical phenomena. In fact, a WSN consists of groups of sensors where each group is responsible for providing information about one or more physical phenomena (e.g., group for collecting temperature data). Sensors are limited in power, computational capacity, and memory. Therefore, a query engine and query operators for processing queries in WSNs should be able to handle resource limitations such as memory and battery life. Adaptability has been explored as an alternative approach when dealing with these conditions. Adaptive query operators (algorithms) can adjust their behavior in response to specific events that take place during data processing. In this paper, we propose an adaptive in-network aggregation operator for query processing in sensor nodes of a WSN, called ADAGA (ADaptive AGgregation Algorithm for sensor networks). The ADAGA adapts its behavior according to memory and energy usage by dynamically adjusting data-collection and data-sending time intervals. ADAGA can correctly aggregate data in WSNs with packet replication. Moreover, ADAGA is able to predict non-performed detection values by analyzing collected values. Thus, ADAGA is able to produce results as close as possible to real results (obtained when no resource constraint is faced). The results obtained through experiments prove the efficiency of ADAGA.     

An energy-efficient protocol for data gathering and aggregation in wireless sensor networks

Data gathering is a major function of many applications in wireless sensor networks (WSNs). The most important issue in designing a data gathering algorithm is how to save energy of sensor nodes while meeting the requirement of applications/users such as sensing area coverage. In this paper, we propose a novel hierarchical clustering protocol (DEEG) for long-lived sensor network. DEEG achieves a good performance in terms of lifetime by minimizing energy consumption for in-network communications and balancing the energy load among all the nodes, the proposed protocol achieves a good performance in terms of network lifetime. DEEG can also handle the energy hetergenous capacities and guarantee that out-network communications always occur in the subregion with high energy reserved. Furthermore, it introduces a simple but efficient approach to cope with the area coverage problem. We evaluate the performance of the proposed protocol using a simple temperature sensing application. Simulation results show that our protocol significantly outperforms LEACH and PEGASIS in terms of network lifetime and the amount of data gathered.

Energy-efficient cooperative data aggregation for wireless sensor networks

Recently, cooperative communication mechanism is shown to be a promising technology to improve the transmit diversity only by a single transceiver antenna. Using this communication paradigm, multiple source nodes are able to coordinate their transmissions so as to obtain energy savings. As data aggregation is one of the most important operations in wireless sensor networks, this paper studies the energy-efficient data aggregation problem through cooperative communication. We first define the cooperative data aggregation (CDA) problem, and formally prove that this problem is NP-Hard. Due to the difficult nature of this problem, we propose a heuristic algorithm MCT for cooperative data aggregation. The theoretical analysis shows that this algorithm can reach the approximate performance ratio of 2. Moreover, the distributed implementation DMCT of the algorithm is also described. We prove that both centralized and distributed algorithms can construct the same topology for cooperative data aggregation. The experimental simulations show that the proposed algorithms will decrease the power consumption by about 12.5% and 66.3% compared with PEDAP and PEGASIS algorithms respectively.     

Secure and energy-efficient data aggregation with malicious aggregator identification in wireless sensor networks

Data aggregation in wireless sensor networks is employed to reduce the communication overhead and prolong the network lifetime. However, an adversary may compromise some sensor nodes, and use them to forge false values as the aggregation result. Previous secure data aggregation schemes have tackled this problem from different angles. The goal of those algorithms is to ensure that the Base Station (BS) does not accept any forged aggregation results. But none of them have tried to detect the nodes that inject into the network bogus aggregation results. Moreover, most of them usually have a communication overhead that is (at best) logarithmic per node. In this paper, we propose a secure and energy-efficient data aggregation scheme that can detect the malicious nodes with a constant per node communication overhead. In our solution, all aggregation results are signed with the private keys of the aggregators so that they cannot be altered by others. Nodes on each link additionally use their pairwise shared key for secure communications. Each node receives the aggregation results from its parent (sent by the parent of its parent) and its siblings (via its parent node), and verifies the aggregation result of the parent node. Theoretical analysis on energy consumption and communication overhead accords with our comparison based simulation study over random data aggregation trees.     

WSN中一种基于时空相关性的网内数据聚合路由协议

无线传感器网络越来越多地应用于各种精确监测中。由于网络中节点的部署密度较大,节点周期性地产生数据,网络中出现大量具有时空相关性的冗余数据,这些冗余数据的传送需要消耗大量的能量。为了减少网络中的数据传输量,降低网络的通信开销,提出了一种基于时空相关性的网内数据聚合路由协议TS-INDAR,通过网内数据聚合技术以及对网络中具有时空相关性数据的控制,减少网路中的数据传输量。TS-INDAR通过路由树的建立最大化重叠路由,以提高网络中数据聚合的几率,通过相关区域和时间抑制对网络中具有时空相关性的数据进行控制,根据事件区域与sink节点之间的距离调整相关区域的大小。与已有路由算法相比,TS-INDAR减少了网络中的通信负载,降低了网络中的能量消耗。仿真结果显示,TS-INDAR在确保监测数据准确性的情况下,网络中的能耗较DRINA算法降低了25%,较EAST算法降低了11.6%。     

Data aggregation in wireless sensor networks using ant colony algorithm

Data aggregation is important in energy constraint wireless sensor networks which exploits correlated sensing data and aggregates at the intermediate nodes to reduce the number of messages exchanged network. This paper considers the problem of constructing data aggregation tree in a wireless sensor network for a group of source nodes to send sensory data to a single sink node. The ant colony system provides a natural and intrinsic way of exploring search space in determining data aggregation. Moreover, we propose an ant colony algorithm for data aggregation in wireless sensor networks. Every ant will explore all possible paths from the source node to the sink node. The data aggregation tree is constructed by the accumulated pheromone. Simulations have shown that our algorithm can reduce significant energy costs.     

基于节点度-限制的数据融合树构建算法

在无线传感网络部分应用中,数据传输必须在指定时延约束下完成.因此,最小化网络时延和最大化网络寿命成为无线传感网络的研究热点.为此,提出基于节点度-限制的数据融合树构建DC-DATC(Degree-Constrained-Based Data Aggregation Tree Constructing)算法.DC-DATC算法减少了高节点度对数据融合时延的影响.依据预设的节点度阈值,只有节点度小于阈值的节点才能加入数据融合树.利用数据融合树传输数据,降低了数据传输量,提高了能量利用率.实验结果表明,DC-DATC算法降低了融合时延,且平衡了网络能耗,最终实现了网络寿命的扩延.     

Prediction-based data aggregation in wireless sensor networks: Combining grey model and Kalman Filter

In many environmental monitoring applications, since the data periodically sensed by wireless sensor networks usually are of high temporal redundancy, prediction-based data aggregation is an important approach for reducing redundant data communications and saving sensor nodes’ energy. In this paper, a novel prediction-based data collection protocol is proposed, in which a double-queue mechanism is designed to synchronize the prediction data series of the sensor node and the sink node, and therefore, the cumulative error of continuous predictions is reduced. Based on this protocol, three prediction-based data aggregation approaches are proposed: Grey-Model-based Data Aggregation (GMDA), Kalman-Filter-based Data Aggregation (KFDA) and Combined Grey model and Kalman Filter Data Aggregation (CoGKDA). By integrating the merit of grey model in quick modeling with the advantage of Kalman Filter in processing data series noise, CoGKDA presents high prediction accuracy, low communication overhead, and relative low computational complexity. Experiments are carried out based on a real data set of a temperature and humidity monitoring application in a granary. The results show that the proposed approaches significantly reduce communication redundancy and evidently improve the lifetime of wireless sensor networks.     

DyDAP: A dynamic data aggregation scheme for privacy aware wireless sensor networks

End-to-end data aggregation, without degrading sensing accuracy, is a very relevant issue in wireless sensor networks (WSN) that can prevent network congestion to occur. Moreover, privacy management requires that anonymity and data integrity are preserved in such networks. Unfortunately, no integrated solutions have been proposed so far, able to tackle both issues in a unified and general environment. To bridge this gap, in this paper we present an approach for dynamic secure end-to-end data aggregation with privacy function, named DyDAP. It has been designed starting from a UML model that encompasses the most important building blocks of a privacy-aware WSN, including aggregation policies. Furthermore, it introduces an original aggregation algorithm that, using a discrete-time control loop, is able to dynamically handle in-network data fusion to reduce the communication load. The performance of the proposed scheme has been verified using computer simulations, showing that DyDAP avoids network congestion and therefore improves WSN estimation accuracy while, at the same time, guaranteeing anonymity and data integrity.     

Energy-efficient and high-accuracy secure data aggregation in wireless sensor networks

Due to the inherent characteristics of resource-constrained sensors, communication overhead is always a major concern in wireless sensor networks (WSNs). Data aggregation is an essential technique to reduce the communication overhead and prolong network lifetime. Since data aggregation results are usually used to make critical decisions, the accuracy of final aggregation results is very important. Furthermore, as wireless sensor networks are increasing being deployed in security-critical applications, we should take security into consideration as well. Therefore, for such applications, data aggregation protocols must be highly energy efficient and highly accurate while being able to prevent an adversary from stealing private data held by each sensor node. In this paper, we propose an energy-efficient and high-accuracy (EEHA) scheme for secure data aggregation. The main idea of our scheme is that accurate data aggregation is achieved without releasing private sensor readings and without introducing significant overhead on the battery-limited sensors. We conduct extensive simulations to evaluate the performance of EEHA. Our analysis and simulations show that EEHA is more efficient and accurate than the existing scheme.     

WSNs中数据融合树的时隙分配算法

周期工作DC(Duty-Cycling)技术,即周期地开/关通信和感测能力,能够有效降低传感节点的活动时间,进而延长无线传感网络寿命.然而,此技术给数据融合提出了挑战.为此,提出免碰撞的数据融合树的时隙分配算法CF-DGSS(Collision-Free Data Aggregation Slots Scheduling Algorithm for Duty-Cycled Wireless Sensor Networks),进而解决基于DC的WSNs的数据融合时隙分配问题.为了解决碰撞问题,CF-DGSS算法给每个节点构建冲突集.每个节点在融合时隙分配过程中,保存自己的冲突集.在分配时隙时,传感节点应当确保与冲突集内节点的数据融合不干扰.仿真结果表明,与其他的分配算法相比,提出的CF-DGSS算法具有低的融合时延.     

Topology control for delay-constraint data collection in wireless sensor networks

Data collection is one of the most important operations in wireless sensor networks. Many practical applications require the real-time data transmission, such as monitoring, tracking, etc. In this paper, we import and define the topology control problem for delay-constraint data collection (TDDC), and then formalize this problem into an integer programming problem. As NP-Hardness of this problem, we present a load-aware power-increased topology control algorithm (namely LPTC) to heuristically solve the problem. The theoretical analysis shows that this algorithm can reach O(1)-approximation ratio for the linear networks. And we also analyze the impact of the delay-constraint on the worst-case for the planar networks. Moreover, this paper designs two localized algorithms, called as SDEL and DDEL, based on the area division for TDDC problem. The experimental results show that LPTC algorithm can save at least 17% power consumptions compared with HBH algorithm in many situations.     

基于簇内分层的无线传感器网络隐私保护数据融合算法

在无线传感器网络中,提供高效的数据融合的同时又保证数据的隐私性是一个具有挑战性的研究问题。提出一个基于簇内二叉分层的完整性和机密性保护的数据融合算法(TIPDA),算法将簇内节点按照二叉树的逻辑结构进行组织,并引入了数据切片的思想完成数据融合,同时将中国剩余定理的思想引入进行端到端的完整性验证。理论分析和实验结果都表明,TIPDA算法可以有效地保护无线传感器网络融合数据的机密性和完整性,且花费较少的通信开销和计算开销。     

Continuous data aggregation and capacity in probabilistic wireless sensor networks

Due to the existence of many probabilistic lossy links in Wireless Sensor Networks (WSNs) (Liu et al., 2010)  [25], it is not practical to study the network capacity issue under the Deterministic Network Model (DNM). A more realistic one is actually the Probabilistic Network Model (PNM). Therefore, we study the Snapshot Data Aggregation (SDA) problem, the Continuous Data Aggregation (CDA) problem, and their achievable capacities for probabilistic WSNs under both the independent and identically distributed (i.i.d.) node distribution model and the Poisson point distribution model in this paper. First, we partition a network into cells and use two vectors to further partition these cells into equivalent color classes. Subsequently, based on the partitioned cells and equivalent color classes, we propose a Cell-based Aggregation Scheduling (CAS) algorithm for the SDA problem in probabilistic WSNs. Theoretical analysis of CAS and the upper bound capacity of the SDA problem show that the achievable capacities of CAS are all order optimal in the worst case, the average case, and the best case. For the CDA problem in probabilistic WSNs, we propose a Level-based Aggregation Scheduling (LAS) algorithm. LAS gathers the aggregation values of continuous snapshots by forming a data aggregation/transmission pipeline on the segments and scheduling all the cell-levels in a cell-level class concurrently. By theoretical analysis of LAS and the upper bound capacity of the CDA problem, we prove that LAS also successfully achieves order optimal capacities in all the cases. The extensive simulation results further validate the effectiveness of CAS and LAS.     

无线传感器网络的数据聚合时机分析

数据聚合是无线传感器网络实现节能的一种重要技术。数据聚合的时机直接影响到数据聚合的准确度和延时,是数据聚合的关键问题之一。建立基于泊松过程的数据聚合模型,分析数据聚合时机的概率特征,提出满足一定概率要求和信息数要求的条件下,数据聚合时机的求解方法。仿真表明,理论分析和模拟实验结果基本相符。该结论为数据聚合时机的分析提供新的思路。     

CPF-EDAS：无线传感器网络中一种基于簇势场的高效数据融合策略*

为了增强无线传感器网络中数据的融合效率,降低节点的能耗,延长网络的寿命,提出一种基于簇势场的高效数据融合策略（CPF-EDAS）。提出的策略是在簇内引入序列势场和在簇头与sink之间引入混合势场来进行数据融合,且簇头根据其局部信息快速构建路线。实验结果表明CPF-EDAS的性能明显优于DP。该方案不但适用于静态路由,且适合火灾监测等动态环境,具有更好的扩展性,可用于各种大规模的无线传感器网络。     

Adapting integrity enforcement techniques for data reconciliation

Integration of data sources opens up possibilities for new and valuable applications of data that cannot be supported by the individual sources alone. Unfortunately, many data integration projects are hindered by the inherent heterogeneities in the sources to be integrated. In particular, differences in the way that real world data is encoded within sources can cause a range of difficulties, not least of which is that the conflicting semantics may not be recognised until the integration project is well under way. Once identified, semantic conflicts of this kind are typically dealt with by configuring a data transformation engine, that can convert incoming data into the form required by the integrated system. However, determination of a complete and consistent set of data transformations for any given integration task is far from trivial. In this paper, we explore the potential application of techniques for integrity enforcement in supporting this process. We describe the design of a data reconciliation tool (LITCHI) based on these techniques that aims to assist taxonomists in the integration of biodiversity data sets. Our experiences have highlighted several limitations of integrity enforcement when applied to this real world problem, and we describe how we have overcome these in the design of our system.