Sensor Network Measurement Technologies Based On End-to-end Measurement

Wireless sensor networks (WSNs) are self-organization networks, which consistof low-cost, low-power tiny sensor nodes that can communicate with each other toperform sensing and data processing cooperatively. And it has gradually become a hotacademic and industrial research topic in recent years and some practical sensor nodehardwares and sensor network oriented operation systems have emerged. As thesensor network has gradually been applied to the actual environment, wireless sensornetwork performance measurement has become an issue of concern to the industry.Due to the large quantity of sensor nodes in wireless sensor network and theinherent stringent bandwidth and energy constraints of sensor nodes, the traditionalinternal measurement methods, which collects sensor network performance statisticaldata from each individual sensor node and processes it at the sink node, is notapplicable to sensor networks, and this makes the sensor network performancemeasurement facing many challenges.In 1999, N. Duffield et al started to study a promising approach, networktomography, which investigates the methods and methodologies to infer the networkinternal link performance from end-to-end measurements. This approach usually doesnot require extra cooperation among the nodes of the network and the deployment ofmeasuring equipments, and incurs minimal overhead into the network. In 2004, G.Hartl et al introduced this promising technology to sensor network performancemeasurement to infer the internal link packet loss rate. However, the research onsensor network tomography is still at its initial stage.This paper concentrated on the methods and methodologies of sensor networkperformance measurement. The main work and the innovations of the study are asfollows.(1) A summary of the research in the network tomography and sensor networktomography was presented. The recent progresses in the areas of research content,system modeling, measurement methods, and inference methods of the networktomography were discussed.(2) Using the network tomography can infer the network logical topology, the network internal link performance and other network properties. Although there aresome wired network topology identification algorithms, no similar topologyidentification algorithm has been used in the wireless sensor network. In this paper, awireless sensor network topology identification algorithm was proposed, which wasbased on the partial ordering relation on the packet receipt/loss between a node and itsdescendant nodes in the data aggregation process. The simulation result shows that itonly needs relatively few dozen of data collection rounds to quite accurately identifythe sensor network topology.(3) A link packet loss Cumulant Generating Function (CGF) algorithm wasproposed and elaborated. In this algorithm, each link packet loss CGF was calculatedfrom the end-to-end path packet loss CGF using the least-squares method. Then basedon the calculated link packet loss CGF, the lossy links were identified using ChernoffBounds. The simulation result shows that the internal link packet loss CGF can beinferred quite accurately, compared to the theoretical value.(4) Maximum likelihood estimation (MLE) is a classical method used in sensornetwork loss tomography. Available studies have shown MLE has some limitationssuch as overfitting. To overcome this problem, the problem of link packet loss rateestimation based on the Bernoulli loss model was formulated as a Bayesian inferenceproblem and a Gibbs sampling algorithm was proposed to solve it. The impacts ofdifferent parameters on the algorithm performance were also discussed. Through thesimulation, it can be safely concluded that the internal link packet loss rate can beinferred quite accurately, compared to the sampled internal link packet loss rate, andthe simulation also shows that the proposed algorithm scales well according to thesensor network size.(5) The Gilbert error model was used to model the sensor link packet losses, theproblem of link packet loss temporal dependency estimation was formulated as aBayesian inference problem, and a Metropolis-Hastings Sampling algorithm was alsoproposed to solve it. The inherent relationships in different packet losses among thesame link were analyzed and impacts of different factors on the algorithmperformance were also discussed. The simulation result shows that the internal linkpacket loss temporal dependency can be inferred quite accurately, compared to thesampled internal link packet loss temporal dependency.(6) The problem of sensor network residual energy measurement was considered, and a residual energy measurement approach based on Bloom filter was proposed.Theoretical analysis and simulations show that the residual energy distribution can beinferred quit accurately, and those distributions with higher spatial correlation can beinferred more accurately. Compared with eScan algorithm proposed by University ofSouthern California, the measurement granularity of the proposed algorithm is finer.