Skip to content

Instantly share code, notes, and snippets.

@bmershon

bmershon/README.md

Last active March 21, 2018 10:13
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save bmershon/dca656bcaa682130cefd to your computer and use it in GitHub Desktop.
Save bmershon/dca656bcaa682130cefd to your computer and use it in GitHub Desktop.
Download ZIP
Holes in Sensor Networks
Raw
README.md

Sensor networks allow for regions to be scanned for the presence of a particular object. Many small devices, each capable of making some measurements, can be distributed over the desired region. The types of measurements a sensor might make include taking temperature readings, detecting electromagnetic frequencies, and recording sound levels. A more complex sensor could process video footage and find valuable information automatically.

A critical consideration for sensor networks is the “blanket” of coverage that is produced. Wherever holes exist in this coverage, it is possible to miss critical information in the region we would like to scan.

If we have sophisticated sensors capable of measuring their exact position, then it is a fairly easy task to compute the coverage of the network. However, if we have simple sensors which can only record local information, then we are presented with the challenge of determining whether the region we are scanning is entirely covered.

Vin de Silva and Robert Ghrist discuss in detail an application of Rips-complexes and homology to the “blanket coverage” problem.

Their paper can be found here.

The simulation we see here is that of a dynamic sensor network and a fixed "fence" of known sensors which form the boundary of a region. We can imagine a forest has a fence of sophisticated sensors placed around a circular region. We would like to monitor this region for fires. A network of sensors is created by dropping cheap radios with thermal and chemical sensors into the region. These sensors move about via wind and animals.

Changing the radius alters the coverage of each individual sensor. Low settings allow for big holes to develop in the coverage. Big holes in the coverage result in large areas where fire could spread undetected. How do we fix this? We could add more sensors. We could increase the range of each sensor. Perhaps we might allow sensors to "reposition" themselves, but then each sensor would likely become very expensive.

Question: For a given radius, is it possible that an "evader" could hide in a hole in the blanket, continuously moving to avoid detection?

Raw
index.html
<!DOCTYPE html><meta charset="utf-8"><title>Dynamic Sensor Network</title><style>svg{position:absolute;top:0;left:0}rect{fill:#000;stroke-width:2px;stroke:orange;fill-opacity:1}.triangle{fill:yellow;stroke-width:1px;stroke:#222;fill-opacity:0.3}form{position:absolute;top:20px;left:20px;z-index:2}</style><body><form> <input id="input" type="range" min="0" max="60" value="20" style="width:240px;"> <label for="input">Sensor Coverage</label></form></body> <script src="https://d3js.org/d3.v3.min.js"></script> <script src="tdad3.js"></script> <script>d3.select("#input").on("input",function(){radius=this.value;});var width=960,height=500;var n_fence=20,radius=20;var fence=d3.range(n_fence).map(function(d,i){return{xloc:Math.cos(Math.PI*2*i/n_fence)*1,yloc:Math.sin(Math.PI*2*i/n_fence)*1,xvel:0,yvel:0};});var data=d3.range(50).map(function(){return{xloc:0,yloc:0,a:Math.random(),b:Math.random(),xOffset:Math.random(),yOffset:Math.random(),theta:Math.random()*Math.PI};});var x=d3.scale.linear().domain([-1.2,1.2]).range([0,height]);var y=d3.scale.linear().domain([-1.2,1.2]).range([0,height]);var svg=d3.select("body").append("svg").attr("width",width).attr("height",height).append("g").attr("transform",function(d){return"translate("+width/4+","+0+")";});var markerSize=10;var square=svg.selectAll("rect").data(fence).enter().append("rect").attr("x",function(d){return x(d.xloc)-markerSize/2}).attr("y",function(d){return y(d.yloc)-markerSize/2}).attr("width",markerSize).attr("height",markerSize).attr("fill","#000");var circle=svg.selectAll("circle").data(data).enter().append("circle").attr("stroke","#000").attr("stroke-width","2px");var cover=svg.selectAll(".cover").data(data).enter().append("circle").attr("fill","#87CEFA").attr("fill-opacity",0.2);var fenceCover=svg.selectAll(".cover").data(fence).enter().append("circle").attr("fill","red").attr("fill-opacity",0.1).attr("cx",function(d){return x(d.xloc)}).attr("cy",function(d){return y(d.yloc)});d3.timer(function(){svg.selectAll("polygon").remove();data.forEach(function(d){d.xloc=d.a*Math.cos(d.theta+d.xOffset*Math.PI);d.yloc=d.b*Math.sin(d.theta+d.yOffset*Math.PI);d.theta+=0.002;});var delaunay=tdad3.rips2d(formatPoints(data.concat(fence)),radius);var triangle=svg.selectAll("polygon").data(delaunay).enter().append("polygon").attr("class","triangle");triangle.attr("points",function(d){var string=d[0][0]+","+d[0][1]+", "+d[1][0]+","+d[1][1]+", "+d[2][0]+","+d[2][1];return string;});cover.attr("r",radius).attr("cx",function(d){return x(d.xloc)}).attr("cy",function(d){return y(d.yloc)});fenceCover.attr("r",radius);circle.attr("cx",function(d){return x(d.xloc)}).attr("cy",function(d){return y(d.yloc)}).attr("r",function(d){return(d.xloc*d.xloc+d.yloc*d.yloc>1)?6:4;}).attr("fill",function(d,i){return(d.xloc*d.xloc+d.yloc*d.yloc>1)?"#fff":"#000"});});function formatPoints(points){var v=[];var length=points.length;for(var i=0;i<length;i++){v.push([x(points[i].xloc),y(points[i].yloc)]);} return v;}</script>
Raw
tdad3.js
!function(){
tdad3 = {};
tdad3.rips2d = _update;
// data: array of points
// radius: limiting radius of balls
function _update(data, _radius) {
var radius = _radius || -1;
var delaunay = d3.geom.delaunay(data);
var triangles = [];
// Delete delaunay triangles whose edges would not exceed our
// given radius, and return the rest of the triangles.
delaunayLength = delaunay.length;
for (var i = 0; i < delaunayLength; i++) {
var triple = delaunay[i];
var a = distanceBetween(triple[0], triple[1]);
var b = distanceBetween(triple[0], triple[2]);
var c = distanceBetween(triple[1], triple[2]);
var max = Math.max(a, Math.max(b, c));
if (radius == -1 || max < radius*2) {
triangles.push(triple);
}
}
return triangles;
}
function distanceBetween(a, b) {
return Math.sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
}();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment