A distributed data clustering algorithm in P2P networks

Clustering is one of the important data mining issues, especially for large and distributed data analysis. Distributed computing environments such as Peer-to-Peer (P2P) networks involve separated/scattered data sources, distributed among the peers. According to unpredictable growth and dynamic nature of P2P networks, data of peers are constantly changing. Due to the high volume of computing and communications and privacy concerns, processing of these types of data should be applied in a distributed way and without central management. Today, most applications of P2P systems focus on unstructured P2P systems. In unstructured P2P networks, spreading gossip is a simple and efficient method of communication, which can adapt to dynamic conditions in these networks. Recently, some algorithms with different pros and cons have been proposed for data clustering in P2P networks. In this paper, by combining a novel method for extracting the representative data, a gossip-based protocol and a new centralized clustering method, a Gossip Based Distributed Clustering algorithm for P2P networks called GBDC-P2P is proposed. The GBDC-P2P algorithm is suitable for data clustering in unstructured P2P networks and it adapts to the dynamic conditions of these networks. In the GBDC-P2P algorithm, peers perform data clustering operation with a distributed approach only through communications with their neighbours. The GBDC-P2P does not need to rely on a central server and it performs asynchronously. Evaluation results demonstrate the superior performance of the GBDC-P2P algorithm. Also, a comparative analysis with other well-established methods illustrates the efficiency of the proposed method.     

Distributed data clustering in sensor networks

Low overhead analysis of large distributed data sets is necessary for current data centers and for future sensor networks. In such systems, each node holds some data value, e.g., a local sensor read, and a concise picture of the global system state needs to be obtained. In resource-constrained environments like sensor networks, this needs to be done without collecting all the data at any location, i.e., in a distributed manner. To this end, we address the distributed clustering problem, in which numerous interconnected nodes compute a clustering of their data, i.e., partition these values into multiple clusters, and describe each cluster concisely. We present a generic algorithm that solves the distributed clustering problem and may be implemented in various topologies, using different clustering types. For example, the generic algorithm can be instantiated to cluster values according to distance, targeting the same problem as the famous k-means clustering algorithm. However, the distance criterion is often not sufficient to provide good clustering results. We present an instantiation of the generic algorithm that describes the values as a Gaussian Mixture (a set of weighted normal distributions), and uses machine learning tools for clustering decisions. Simulations show the robustness, speed and scalability of this algorithm. We prove that any implementation of the generic algorithm converges over any connected topology, clustering criterion and cluster representation, in fully asynchronous settings.     

Energy-efficient clustering in lossy wireless sensor networks

Recent experimental studies have revealed that a large percentage of wireless links are lossy and unreliable for data delivery in wireless sensor networks (WSNs). Such findings raise new challenges for the design of clustering algorithms in WSNs in terms of data reliability and energy efficiency. In this paper, we propose distributed clustering algorithms for lossy WSNs with a mobile collector, where the mobile collector moves close to each cluster head to receive data directly and then uploads collected data to the base station. We first consider constructing one-hop clusters in lossy WSNs where all cluster members are within the direct communication range of their cluster heads. We formulate the problem into an integer program, aiming at maximizing the network lifetime, which is defined as the number of rounds of data collection until the first node dies. We then prove that the problem is NP-hard. After that, we propose a metric-based distributed clustering algorithm to solve the problem. We adopt a metric called selection weight for each sensor node that indicates both link qualities around the node and its capability of being a cluster head. We further extend the algorithm to multi-hop clustering to achieve better scalability. We have found out that the performance of the one-hop clustering algorithm in small WSNs is very close to the optimal results obtained by mathematical tools. We have conducted extensive simulations for large WSNs and the results demonstrate that the proposed clustering algorithms can significantly improve the data reception ratio, reduce the total energy consumption in the network and prolong network lifetime compared to a typical distributed clustering algorithm, HEED, that does not consider lossy links.     

使用部署知识的异构传感器网络有效成簇算法

成簇算法是传感器网络中减少能量消耗的一种关键技术,它能够增强网络的扩展性和延长网络的生存时间。异构传感网络在能量节约方面的性能更好。提出一种适应异构无线传感器网络的分布式能量有效的成簇方案DEECUDK。该方案首先利用部署知识部署节点,使能量在整个监测区域分布比较均匀,然后以节点的剩余能量与传感半径之内的节点的剩余覆盖能量为主参数,其相邻节点个数为辅参数来选举簇头节点。较高初始能量、剩余能量和相邻节点数多的节点比其他节点拥有更多的机会成为簇头节点,并引入活动节点判别式,不需要增加任何开销来减少簇内冗余数据量,从而使网络能量均匀消耗,延长网络的生存时间。通过模拟实验结果,与现有的异构传感网络成簇算法相比,新的算法在网络生存时间与网络吞吐量方面有着更好的性能。     

Peer sampling gossip-based distributed clustering algorithm for unstructured P2P networks

Clustering, as an unsupervised learning method and an important process in data mining, is an aspect of large and distributed data analysis. In many applications, such as peer-to-peer systems, huge volumes of data are distributed between multiple sources. Analysis of these volumes of data and identifying appropriate clusters is challenging due to transmission, processing and storage costs. In this paper, a gossip-based distributed clustering algorithm for P2P networks called Efficient GBDC-P2P is proposed, based on an improved gossip communicative approach by combining the peer sampeling and CYCLON protocol and the idea of partitioning-based data clustering. This algorithm is appropriate for data clustering in unstructured P2P networks, and it is adapted to the dynamic conditions of these networks. In the Efficient GBDC-P2P algorithm, distributed peers perform clustering operation in a distributed way only through local communications with their neighbors. Our approach does not rely on the central server to carry out data clustering task and without the need to synchronize operations. Evaluation results verify the efficiency of our proposed algorithm for data clustering in unstructured P2P networks. Furthermore, comparative analyses with other well-established distributed clustering approaches demonstrate the superior accuracy of the proposed method.

     

Parametric calibration of speed-density relationships in mesoscopic traffic simulator with data mining

Speed-density relationships are used by mesoscopic traffic simulators to represent traffic dynamics. While classical speed-density relationships provide useful insights into the traffic dynamics problem, they may be restrictive for such applications. This paper addresses the problem of calibrating speed-density relationship parameters using data mining techniques, and proposes a novel hierarchical clustering algorithm based on K-means clustering. By combining K-means with agglomerative hierarchical clustering, the proposed new algorithm is able to reduce early-stage errors inherent in agglomerative hierarchical clustering resulted in improved clustering performance. Moreover, in order to improve the precision of parametric calibration, densities and flows are utilized as variables. The proposed approach is tested against sensor data captured from the 3rd Ring Road of Beijing. The testing results show that the performance of our algorithm is better than existing solutions.     

异构传感器网络的分布式能量有效成簇算法

为了延长网络的生存时间,需要设计能量有效的协议,以适应传感器网络的特点.成簇算法是传感器网络中减少能量消耗的一种关键技术,它能够增强网络的扩展性和延长网络的生存时间.研究了异构传感器网络中成簇算法在节省能量方面的性能,提出一种适应异构无线传感器网络的分布式能量有效的成簇方案.此方案基于节点剩余能量与网络节点的平均能量的比例来选举簇头节点.较高初始能量和剩余能量的节点比低能量节点拥有更多的机会成为簇头节点,从而使网络能量均匀消耗,延长网络的生存时间.模拟实验结果显示,与现有的重要成簇方案相比,新的成簇算法在异构网络下提供了更长的网络生存时间和更大的网络有效吞吐量.     

一种基于能量估计的异构传感器网络分簇算法

分簇算法是一种延长无线传感网络生命期的重要技术,本文提出了一种新的基于分布式能量估计的分簇算法,它可以针对能量异构传感器网络的不同场景而应用,更有效地利用能量。仿真结果表明,这种新的分簇算法能够有效地延长网络生命期,并提高网络的数据吞吐量。     

A distributed energy-efficient clustering protocol for wireless sensor networks

Minimizing energy dissipation and maximizing network lifetime are among the central concerns when designing applications and protocols for sensor networks. Clustering has been proven to be energy-efficient in sensor networks since data routing and relaying are only operated by cluster heads. Besides, cluster heads can process, filter and aggregate data sent by cluster members, thus reducing network load and alleviating the bandwidth. In this paper, we propose a novel distributed clustering algorithm where cluster heads are elected following a three-way message exchange between each sensor and its neighbors. Sensor’s eligibility to be elected cluster head is based on its residual energy and its degree. Our protocol has a message exchange complexity of O(1) and a worst-case convergence time complexity of O(N). Simulations show that our algorithm outperforms EESH, one of the most recently published distributed clustering algorithms, in terms of network lifetime and ratio of elected cluster heads.     

多级能量异构传感器网络的负载均衡成簇算法

在多级能量异构无线传感器网络中,节点的初始能量在一定的范围内随机分布,负载均衡和降低能耗是能量异构网络成簇算法的一个重要挑战.现有的分布式成簇算法主要是针对能量同构或二级异构网络设计的,无法实现节点能量多级异构时的负载均衡,因此提出了适用于多级能量异构传感网络的负载均衡成簇算法LBCA(load balance clustering algorithm).LBCA根据传感器网络的能量分布情况选择簇头节,最和实现负载均衡,可以有效地延长网络的稳定周期.簇头选择过程中,当探测区域能量分布均衡时,拥有较低平均通信能耗的节点将优先成为簇头节点,有利于降低探测区域内的总通信能耗;当探测区域能量分布不均衡时,具有较高剩余能量的节点将优先成为簇头节点,有利于实现探测区域内的负载均衡.将LBCA与主要的分布式成簇方案进行了比较,模拟实验结果显示,在多级能量异构传感器网络中,LBCA可以更好地实现负载均衡,极大地提高网络的稳定周期.     

Distributed anomaly detection for industrial wireless sensor networks based on fuzzy data modelling

Modern infrastructure increasingly depends on large computerized systems for their reliable operation. Supervisory Control and Data Acquisition (SCADA) systems are being deployed to monitor and control large scale distributed infrastructures (e.g. power plants, water distribution systems). A recent trend is to incorporate Wireless Sensor Networks (WSNs) to sense and gather data. However, due to the broadcast nature of the network and inherent limitations in the sensor nodes themselves, they are vulnerable to different types of security attacks. Given the critical aspects of the underlying infrastructure it is an extremely important research challenge to provide effective methods to detect malicious activities on these networks. This paper proposes a robust and scalable mechanism that aims to detect malicious anomalies accurately and efficiently using distributed in-network processing in a hierarchical framework. Unsupervised data partitioning is performed distributively adapting fuzzy c-means clustering in an incremental model. Non-parametric and non-probabilistic anomaly detection is performed through fuzzy membership evaluations and thresholds on observed inter-cluster distances. Robust thresholds are determined adaptively using second order statistical knowledge at each evaluation stage. Extensive experiments were performed and the results demonstrate that the proposed framework achieves high detection accuracy compared to existing data clustering approaches with more than 96% less communication overheads opposed to a centralized approach.     

An Energy Efficient Clustering Scheme for Data Aggregation in Wireless Sensor Networks

In wireless sensor networks, a clustering scheme is helpful in reducing the energy consumption by aggregating data at intermediate sensors. This paper discusses the important issue of energy optimization in hierarchically-clustered wireless sensor networks to minimize the total energy consumption required to collect data. We propose a comprehensive energy consumption model for multi-tier clustered sensor networks, in which all the energy consumptions not only in the phase of data transmissions but also in the phase of cluster head rotations are taken into account. By using this new model, we are able to obtain the solutions of optimal tier number and the resulted optimal clustering scheme on how to group all the sensors into tiers by the suggested numerical method. This then enables us to propose an energy-efficiency optimized distributed multi-tier clustering algorithm for wireless sensor networks. This algorithm is theoretically analyzed in terms of time complexity. Simulation results are provided to show that, the theoretically calculated energy consumption by the new model matches very well with the simulation results, and the energy consumption is indeed minimized at the optimal number of tiers in the multi-tier clustered wireless sensor networks.     

EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks

In recent years, there has been a growing interest in wireless sensor networks. One of the major issues in wireless sensor network is developing an energy-efficient clustering protocol. Hierarchical clustering algorithms are very important in increasing the network’s life time. Each clustering algorithm is composed of two phases, the setup phase and steady state phase. The hot point in these algorithms is the cluster head selection. In this paper, we study the impact of heterogeneity of nodes in terms of their energy in wireless sensor networks that are hierarchically clustered. We assume that a percentage of the population of sensor nodes is equipped with the additional energy resources. We also assume that the sensor nodes are randomly distributed and are not mobile, the coordinates of the sink and the dimensions of the sensor field are known. Homogeneous clustering protocols assume that all the sensor nodes are equipped with the same amount of energy and as a result, they cannot take the advantage of the presence of node heterogeneity. Adapting this approach, we introduce an energy efficient heterogeneous clustered scheme for wireless sensor networks based on weighted election probabilities of each node to become a cluster head according to the residual energy in each node. Finally, the simulation results demonstrate that our proposed heterogeneous clustering approach is more effective in prolonging the network lifetime compared with LEACH.     

EEMC: An energy-efficient multi-level clustering algorithm for large-scale wireless sensor networks

Wireless sensor networks can be used to collect environmental data from the interested area using multi-hop communication. As sensor networks have limited and non-rechargeable energy resources, energy efficiency is a very important issue in designing the topology, which affects the lifetime of sensor networks greatly. In this paper, the energy consumption is modeled and compared under the flat scheme and the clustering scheme, respectively. Motivated by the analysis, we propose an energy-efficient multi-level clustering algorithm called EEMC, which is designed to achieve minimum energy consumption in sensor networks. The cluster head election scheme is also considered in EEMC. EEMC terminates in O(log log N) iterations given N nodes. When the path loss exponent is 2, EEMC also achieves minimum latency. We focus on the case where sink node is remotely located and sensor nodes are stationary. Simulation results demonstrate that our proposed algorithm is effective in prolonging the network lifetime of a large-scale network, as well as low latency and moderate overhead across the network.     

无线传感器/执行器网络中能量有效的实时分簇路由协议

无线传感器/执行器网络(WSANs)主要应用于自动控制领域,实时性问题是其面临的首要挑战.根据实际环境中的节点部署情况,建立了系统模型;研究了分簇策略与功率控制技术对于自组织网络实时性的影响,提出了一种可适用于WSANs的能量有效的实时分簇路由协议--RECRP协议.该协议采用二级成簇策略使网络中的各类节点稳定分簇.分簇后的各类节点具有不同发射功率,利用执行器节点的强大通信能力有效降低网络延时.采用能量有效性算法使网络中的传感器节点轮换担任簇首,从而使网络能量均匀消耗,延长网络的生存时间.实验结果证明,在WSANs中RECRP协议可使网络稳定分簇,并且在网络的实时性与能量有效性方面与现有典型路由协议相比具有更优越的性能.     

Approximation schemes for load balanced clustering in wireless sensor networks

Clustering sensor nodes is an efficient technique to improve scalability and life time of a wireless sensor network (WSN). However, in a cluster based WSN, the leaders (cluster heads) consume more energy due to some extra load for various activities such as data collection, data aggregation, and communication of the aggregated data to the base station. Therefore, balancing the load of the cluster heads is a crucial issue for the long run operation of the WSNs. In this paper, we first present a load balanced clustering scheme for wireless sensor networks. We show that the algorithm runs in O(nlogn) time for n sensor nodes. We prove that the algorithm is optimal for the case in which the sensor nodes have equal load. We also show that it is a polynomial time 2-approximation algorithm for the general case, i.e., when the sensor nodes have variable load. We finally improve this algorithm and propose a 1.5-approximation algorithm for the general case. The experimental results show the efficiency of the proposed algorithm in terms of the load balancing of the cluster heads, execution time, and the network life.     

一种多属性目标监测的无线感知网络覆盖算法

本文研究了一种无线感知网络应用中多属性目标的覆盖问题。这种覆盖问题与单一类型数据的目标不同,其待测区域中的每个目标同时包含多种类型的现场数据。如果布置一个无线感知网络去担任监测任务,其节点需要配置多种不同类型的传感器单元。针对这种需要采集多种类型的数据才能对目标进行监测的无线感知网络的应用,节能而有效的的覆盖目标更是一个突出的问题。本文首先用ILP模型将问题进行了形式化,然后通过设计一种分布式算法求得问题了模拟仿真。仿真结果表明,这种分布式算法比直接求解ILP求出的网络寿命很接近。由于直接求解ILP问题必须依靠中心节点完成,对于节点较多并且电量受限的无线感知网络,这种分布式算法更适合。     

BPEC:无线传感器网络中一种能量感知的分布式分簇算法

无线传感器网络的大面积铺设以及数据融合的需求,促使必须有效地组织网络的拓扑结构,以达到均衡负载、延长网络的生命周期的目标.分簇已被证实是将网络组织成层次相连结构的有效方式.提出了一种新的以邻居节点的平均剩余能量与节点本身的剩余能量的比值作为竞争簇头的主要参数,以节点的"度"作为节点竞争簇头辅助参数的节能分布式分簇算法BPEC.如果执行BPEC算法,整个网络的广播消息量复杂度为O(n),整个网络的时间复杂度为O(1).证明了由BPEC算法产生的簇头集合是一个最大独立集,簇头集合能覆盖网络的所有节点.当节点足够多时,仿真实验结果表明,簇头集合的尺寸大小与理论推导值十分接近.     

Molecular dynamics-like data clustering approach

Based on the molecular kinetic theory, a molecular dynamics-like data clustering approach is proposed in this paper. Clusters are extracted after data points fuse in the iterating space by the dynamical mechanism that is similar to the interacting mechanism between molecules through molecular forces. This approach is to find possible natural clusters without pre-specifying the number of clusters. Compared with 3 other clustering methods (trimmed k-means, JP algorithm and another gravitational model based method), this approach found clusters better than the other 3 methods in the experiments.     

EQOWSN: Evolutionary-based query optimization over self-organized wireless sensor networks

In this paper, a new approach has been introduced that integrates an evolutionary-based mechanism with a distributed query sensor cover algorithm for optimal query execution in self-organized wireless sensor networks (WSN). An algorithm based on an evolutionary technique is proposed, with problem-specific genetic operators to improve computing efficiency. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of spatial queries. Any reduction in communication cost would result in an efficient use of battery energy, which is very limited in sensors. Our objective is to self-organize the network, in response to a query, into a topology that involves an optimal subset of sensors that is sufficient to process the query subject to connectivity, coverage, energy consumption, cover size and communication overhead constraints. Query processing must incorporate energy awareness into the system by reducing the total energy consumption and hence increasing the lifetime of the sensor cover, which is beneficial for large long running queries. Experiments have been carried out on networks with different sensors Transmission radius, different query sizes, and different network configurations. Through extensive simulations, we have shown that our designed technique result in substantial energy savings in a sensor network. Compared with other techniques, the results demonstrated a significant improvement of the proposed technique in terms of energy-efficient query cover with lower communication cost and lower size.