93 research outputs found
Network Boundary Identification using Local Information
No full textDetection of nodes on the network boundary is necessary for correct operation in many wireless applications. Many virtual coordinate constructions rely on the furthest set of nodes as beacons, and sensing applications may find useful the knowledge of the network edge. In this paper we propose local convex view (lcv) as a means to identify nodes close to the network edge. It is based on the idea that -hulls can capture the shape of a set of points, and motivated by the hypothesis that some structural information relevant to the network is buried within view of many nodes. The lcv differs from most previous methods in that it is a localized algorithm. Nodes using lcv establish neighbourhood coordinates where no location information is available a priori. In those cases where needed information is missing, we adopt a simple probabilistic model to decide the boundary status of a node. We identify two metrics for evaluation, and compare via simulation the performance of lcv against two methods with similar properties. In our experiments we find lcv to be consistent in its performance, and resilient to the impediments facing other methods
Why everyone should have to learn computer programming
No full textFirst paragraph: News that numerous cathedrals are offering short courses in Latin is a reminder of the long decline of the language over the years. It was a core subject in the British education system until fairly recently – and not because anyone planned to speak it, of course. It was believed to offer valuable training for intellectual composition, as well as skills and thinking that were transferable to other fields. Access this article on The Conversation website: https://theconversation.com/why-everyone-should-have-to-learn-computer-programming-6232
Localised alpha-shape computations for boundary recognition in sensor networks
No full textIntuitively, many wireless and sensing applications benefit from knowledge of network boundaries. Many virtual coordinate constructions rely on the furthest set of nodes as beacons. Network edges may also bound routing holes in the network, regions of failure due to environmental effects, or indicate the need for additional deployment. In this paper we solve the edge detection problem locally using a geometric structure called the alpha-shape (αα-shape). For a disc of radius 1/α1/α, the αα-shape consists of nodes (and joining edges) that sit on the boundary of the discs that contain no other nodes in the network. In the simplest terms a node decides it is on a network boundary by asking the following question: "Do I sit on the boundary of a disc of radius 1/α1/α that contains no other nodes in the network?" We show that using only local communications our algorithm is provably correct. Boundary nodes may further participate to reduce unwanted detail. We show via simulation that our algorithm identifies meaningful boundaries even in networks of low-density and non-uniform distribution
An Analysis of Planarity in Face-Routing
No full textIn this report we investigate the limits of routing according to left- or right-hand rule (LHR). Using LHR, a node upon receipt of a message will forward to the neighbour that sits next in counter-clockwise order in the network graph. When used to recover from greedy routing failures, LHR guarantees success if implemented over planar graphs. This is often referred to as face or geographic routing. In the current body of knowledge it is known that if planarity is violated then LHR is guaranteed only to eventually return to the point of origin. Our work seeks to understand why a non-planar environment stops LHR from making delivery guarantees. Our investigation begins with an analysis to enumerate all node con gurations that cause intersections. A trace over each con guration reveals that LHR is able to recover from all but a single case, the `umbrella' con guration so named for its appearance. We use this information to propose the Prohibitive Link Detection Protocol (PDLP) that can guarantee delivery over non-planar graphs using standard face-routing techniques. As the name implies, the protocol detects and circumvents the `bad' links that hamper LHR. The goal of this work is to maintain routing guarantees while disturbing the network graph as little as possible. In doing so, a new starting point emerges from which to build rich distributed protocols in the spirit of protocols such as CLDP and GDSTR
Prohibitive-link Detection and Routing Protocol
No full textIn this paper we investigate the limits of routing according to left- or righthand rule (LHR). Using LHR, a node upon receipt of a message will forward to the neighbour that sits next in counter-clockwise order in the network graph. When used to recover from greedy routing failures, LHR guarantees success if implemented over planar graphs. We note, however, that if planarity is violated then LHR is only guaranteed to eventually return to the point of origin. Our work seeks to understand why. An enumeration and analysis of possible intersections leads us to propose the Prohibitive-link Detection and Routing Protocol (PDRP) that can guarantee delivery over non-planar graphs. As the name implies, the protocol detects and circumvents the ‘bad' links that hamper LHR. Our implementation of PDRP in TinyOS reveals the same level of service as face-routing protocols despite preserving most intersecting links in the network
Simple geometric constructs for routing and boundary detection in sensor networks
No full textMicro-sensor and radio technologies now permit the manufacture of cheap sensor or embedded devices deployable en masse. Applications appear in a diverse set of environments for far reaching applications including but not limited to structural monitoring, target tracking, and early warning systems. When deployed to create a sensor network, have no foreknowledge of their environment. In a network of this type traditional networking techniques are unsuitable. In general, sensing and embedded devices are shaped by four constraints: limited power supply, small memory, unattended operation, and the error-prone nature of wireless communications.
Our work is motivated by the hypothesis that within view of each node are geometric features that impact network characteristics and behaviour. The central objective in this thesis is to investigate the geometry of the network graphs. Doing so allows us to identify some of the unique features of the network that constrain larger problems.
We first propose boundary detection solutions using two well-known structures. First with the convex hull we build a localised heuristic, local convex view (lcv), that is designed on the premise that a node on the convex hull of a small region of the network is likely on the convex hull of the whole network. We show positive results via analysis and simulation and discover that the geometric properties are directly responsible for its resilience to error. We propose further the alpha-hull. whose structure can reveal details in the 'shape' of a set of points. We find that by selecting the alpha-parameter carefully, it is possible to infer the network-wide alpha-hull from local communications and computations.
We also investigate the limits of routing according to left- or right-hand rule (LHR). Using LHR, a node upon receipt of a message will forward to the neighbour that sits next in counter-clockwise order in the network graph. When used to recover from greedy routing failures, LHR guarantees success if implemented over planar graphs. We identify network constraints that lead us to propose the Prohibitive-link Detection and Routing Protocol (PDRP) that can guarantee delivery over non-planar graphs. As the name implies, the protocol detects and circumvents 'bad' links. Our implementation of PDRP reveals the same level of service as face-routing protocols despite preserving most intersecting links in the network
Simple geometric constructs for routing and boundary detection in sensor networks
No full textMicro-sensor and radio technologies now permit the manufacture of cheap sensor or embedded devices deployable en masse. Applications appear in a diverse set of environments for far reaching applications including but not limited to structural monitoring, target tracking, and early warning systems. When deployed to create a sensor network, have no foreknowledge of their environment. In a network of this type traditional networking techniques are unsuitable. In general, sensing and embedded devices are shaped by four constraints: limited power supply, small memory, unattended operation, and the error-prone nature of wireless communications.
Our work is motivated by the hypothesis that within view of each node are geometric features that impact network characteristics and behaviour. The central objective in this thesis is to investigate the geometry of the network graphs. Doing so allows us to identify some of the unique features of the network that constrain larger problems.
We first propose boundary detection solutions using two well-known structures. First with the convex hull we build a localised heuristic, local convex view (lcv), that is designed on the premise that a node on the convex hull of a small region of the network is likely on the convex hull of the whole network. We show positive results via analysis and simulation and discover that the geometric properties are directly responsible for its resilience to error. We propose further the alpha-hull. whose structure can reveal details in the 'shape' of a set of points. We find that by selecting the alpha-parameter carefully, it is possible to infer the network-wide alpha-hull from local communications and computations.
We also investigate the limits of routing according to left- or right-hand rule (LHR). Using LHR, a node upon receipt of a message will forward to the neighbour that sits next in counter-clockwise order in the network graph. When used to recover from greedy routing failures, LHR guarantees success if implemented over planar graphs. We identify network constraints that lead us to propose the Prohibitive-link Detection and Routing Protocol (PDRP) that can guarantee delivery over non-planar graphs. As the name implies, the protocol detects and circumvents 'bad' links. Our implementation of PDRP reveals the same level of service as face-routing protocols despite preserving most intersecting links in the network
Implementing real-time transport services over an ossified network
No full textReal-time applications require a set of transport services not currently provided by widely-deployed transport protocols. Ossification prevents the deployment of novel protocols, restricting solutions to protocols using either TCP or UDP as a substrate. We describe the transport services required by real-time applications. We show that, in the short-term (i.e., while UDP is blocked at current levels), TCP offers a feasible substrate for providing these services. Over the longer term, protocols using UDP may reduce the number of networks blocking UDP, enabling a shift towards its use as a demultiplexing layer for novel transport protocols
TCP Hollywood: An Unordered, Time-Lined, TCP for Networked Multimedia Applications
No full textOssification of the transport-layer limits networked multimedia applications to use TCP or UDP, despite standardisation of new transport protocols that better support their requirements. To improve transport for these applications, we present TCP Hollywood, an unordered, time-lined, TCP variant designed to support real-time multimedia traffic while being widely deployable. Analysis of the protocol indicates that it increases the utility of the network in lossy conditions where total one-way delay is constrained, such as with telephony applications and low-latency video streaming. This allows retransmissions to be useful in cases where they are not with standard TCP, improving the timely good-put of the protocol and reducing overheads. Initial experiments show that TCP Hollywood is deployable on the Internet, successfully operating on all major fixed and mobil
- …
