Monitoring topological changes in dynamic regions
Any nodes that detect a change in their sensed value inform neighbors of the change. A node maintains the sensed value for its one-hop neighbors. Based on its own sensed value and the sensed value of its neighbors, a node determines whether a region has appeared, disappeared, split or merged. Each region is assigned with a region ID, which will be disseminated to all boundary nodes of the region. When a region is split into two parts, each part will get a new region ID from the node where the split happens.
Protocol 6.9
Code designed by Matt Duckham. Additional coding by Alan Both and Hai Ruo Xie.
Copyright 2011, 2012 Matt Duckham
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License http://www.gnu.org/licenses/ for more details.
The formal specification procedure used for all the protocols on this site is based on the standard distributed systems approach of Nicola Santoro (see Santoro, N. Design and Analysis of Distributed Algorithms. Wiley, Hoboken, NJ. 2007.) For more details on the protocol specification style, please refer to the book accompanying book for this website, Decentralized Spatial Computing: Foundations of Geosensor Networks.
;; Copyright 2011, 2012 Matt Duckham ;; ;; This program is free software: you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation, either version 3 of the License, or ;; (at your option) any later version. ;; ;; This program is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; ;; You should have received a copy of the GNU General Public License ;; along with this program. If not, see <http://www.gnu.org/licenses/>. __includes["../gsn.nls" "../env.nls"] ;; Last time that a region is changed, maximum distance of a link globals [region_timestamp c] ;; Define a new breed of turtle called motes breed [motes mote] ;; Each mote can store the local variable s which is the sensed value, s_l which is the previous sensed value ;; d is the sensed value of neighbors, rid is the region id motes-own [s s_l d rid] ;; System setup and initialization to initialize if (max-pxcor - min-pxcor) * (max-pycor - min-pycor) <= netsize [ show "The number of motes should be smaller than the number of patches. Please reduce the Netsize or increase the number of patches." stop ] ;; *********Create maximal planar graph************ ;; Distribute motes evenly and randomly in the whole area ;; Divide the whole area into 'netsize' virtual tiles let tile_size (max-pxcor - min-pxcor) * (max-pycor - min-pycor) / netsize ;; Size of a tile let xy_ratio (max-pxcor - min-pxcor) / (max-pycor - min-pycor) ;; Ratio of width versus height let th sqrt (tile_size / xy_ratio) ;; Height of a tile let tw sqrt (tile_size * xy_ratio) ;; Width of a tile ;; Place a mote at a random location within a tile let mID 0 ;; Mote ID let px min-pxcor + 0.5 * tw while [px <= max-pxcor][ let py min-pycor + 0.5 * th while [py <= max-pycor][ let inc_px random-float tw let inc_py random-float th ask mote mID [ setxy (px + inc_px - 0.5 * tw) (py + inc_py - 0.5 * th) ] set mID mID + 1 set py py + th ] set px px + tw ] ;; Adjust the positions of motes to ensure that no patch has more than one mote while [any? patches with [(count motes-here) > 1]] [ ;; No patch should contain more than one mote ask patches with [(count motes-here) > 1][ ask motes-here [ let inc_px random-float 1 let inc_py random-float 1 setxy (xcor + inc_px - 0.5) (ycor + inc_py - 0.5) ] ] ] ;; Create links between motes set c (sqrt (tw * tw + th * th)) * 2 ;; To keep the graph balanced, set a limit of the length of links create-udg ;; The MPG is a sub-graph of the UDG create-gg ;; The GG is a sub-graph of the MPG ;; Some links that have been removed earlier may need to be re-created. Add links to complete the graph based on cyc function. repeat 2 [completeMPG] ;; Check to ensure that every mote has two or more linked neighbor if any? motes with [count link-neighbors < 2] [ show "There are one or more motes which have less than two linked neighbors. Re-generating the network..." setup initialize stop ] ;; *********Finished creating maximal planar graph************ ;; Initialize local data ask motes [ set d [] foreach sort link-neighbors [ set d lput (list [who] of ? 0) d ;; Init. to d(i)=0 ] set rid 0 ;; Init. to rid:=0 set color white become "IDLE" ;; Initialize to IDLE first ] set region_timestamp 0 ;; Reset the timestamp of region change end ;; Complete maximal planar graph: ensure that there is a link between any pair of adjacent linked neighbors A and B (A=cyc(B)) of every mote. to completeMPG ask motes [ foreach sort link-neighbors [ let nbr1ID [who] of ? let nbr2ID cyc nbr1ID while [ [color] of link who nbr2ID = blue ] [ ;; Ignore blue links set nbr2ID cyc nbr2ID ] if is-link? link nbr1ID nbr2ID = false and nbr1ID != nbr2ID [ ;; Only form new links ask mote nbr1ID [create-link-with (mote nbr2ID)] ask link nbr1ID nbr2ID [ ifelse link-length > c [die] ;; Kill link if it exceeds maximum distance [set color blue] ;; Newly added links are blue ] ] ] ] ;; Removing intersecting links from the MPG ask links [ if color != blue [stop] ;; Only considering the newly added links let link1_end1 [who] of end1 let link1_end2 [who] of end2 ask other links [ if color = red [stop] ;; Not considering links which are already marked for deletion let link2_end1 [who] of end1 let link2_end2 [who] of end2 if (link1_end1 != link2_end1) and (link1_end2 != link2_end2) and (link1_end2 != link2_end1) and (link1_end1 != link2_end2) [ let p_a list [xcor] of (mote link1_end1) [ycor] of (mote link1_end1) let p_b list [xcor] of (mote link1_end2) [ycor] of (mote link1_end2) let p_c list [xcor] of (mote link2_end1) [ycor] of (mote link2_end1) let p_d list [xcor] of (mote link2_end2) [ycor] of (mote link2_end2) if intersect p_a p_b p_c p_d [ ;; If two links intersect, highlight the longer one ifelse ([link-length] of link link1_end1 link1_end2) <= ([link-length] of link link2_end1 link2_end2) [ask link link2_end1 link2_end2 [set color red]] [ask link link1_end1 link1_end2 [set color red]] ] ] ] ] ask links [ ifelse color = red [die] ;; Remove the highlighted links [set color grey] ;; Remaining links will be grey ] end ;; Runs the region monitoring algorithm to go if count patches <= netsize [ show "The number of motes should be smaller than the number of patches. Please reduce the Netsize or increase the number of patches." stop ] ask motes [ step ] mote_labels ;; Changes the labels of the motes based on the MoteLabel dropdown list tick ;; Change region at certain rate if (ticks - region_timestamp) >= RegionChangeInterval [ ifelse not any? patches with [region = ["A"]] [ make-single-region 1 ;; Create a region when there is no region ] [ ;; Randomly make one of the three changes: create a region, evolve a region or shrink a region let rnd random-float 1 if rnd < 0.1 [make-single-region 1] ;; Create a new region if 0.1 <= rnd and rnd < 0.9 [evolve-region-special ["A"] RegionSize] ;; Incrementally change the existing region if rnd > 0.9 [ ask one-of patches with [(region = ["A"]) and (any? neighbors4 with [region = []])] [ set region [] ;;Remove the patch from the region set pcolor white ;;Restore color ] FillHole ] ] ask motes [ ;Update sensed value ifelse [region] of patch-here = ["A"] [set s 1] [set s 0] ] set region_timestamp ticks ;; Update the timestamp of region change ] end ;; Get set I (IDs of neighbors n where d(n)=0 and d(cyc(n))=1) to-report CI let c_i [] ;; A list of the IDs of neighbors satisfying the criteria of I foreach d [ let d_n (item 1 ?) ;Reading of neighbor n let cyc_n cyc (item 0 ?) ;ID of next neighbor anticlockwise let d_cyc_n item 1 item 0 (filter [item 0 ? = cyc_n] d) if d_n = 0 and d_cyc_n = 1 [ set c_i lput (item 0 ?) c_i ] ] report c_i end ;; Unique new region identifier function u to-report id_func [mt] let value (word mt (" at ") ticks) report value end ;; ;; Mote protocols ;; ;; Step through the current state to step if state = "IDLE" [ step_IDLE stop ] if state = "BNDY" [ step_BNDY stop ] if state = "PNCH" [ step_PNCH stop ] end ;; Motes in the IDLE state an upd8 message when their sensed value changes ;; Motes receiving the upd8 message update their d table with the received sensed value ;; and if they are within the region, send an idnt message to neighbors with ??? ;; and transition to the BNDY state to step_IDLE if s_l != s [ ;; When sensed value changes set s_l s ;; Update the previous sensed value so this part only executes once broadcast (list "upd8" who s) ;; Broadcast sensed value and identifier ifelse length filter [item 1 ? = 0] d = count my-links [ ;; All neighbors sense value 0 set rid id_func who become "BNDY" type "Region appeared at mote " type who type ". Rid: " type rid type "\n" ;; Report region rid appeared ] [ ;; Not all neighbors sense value 0 let c_i CI if length c_i = 1 [ ;; Only one sequence of neighbors which are not part of the region send (list "idnt" who) (mote cyc item 0 c_i) become "BNDY" ] if length c_i >= 2 [ ;; Two or more sequences of neighbors which are not part of the region (region merge) set rid id_func who foreach c_i [ send (list "regn" rid who) (mote cyc ?) ] type "Region merged at mote " type who type ". Rid: " type rid type "\n" ;; Report region merge detected become "PNCH" ] ] stop ] if has-message "upd8" [ ;; Received upd8 message let msg received "upd8" let i' item 1 msg let s' item 2 msg let NewRecord (list i' s') let OldRecord first filter [item 0 ? = i'] d ;; Find record where i = i' set d replace-item (position OldRecord d) d NewRecord ;; set d(i') as s if s = 1 [ let c_i CI if length c_i = 1 [ send (list "idnt" who) (mote cyc item 0 c_i) become "BNDY" ] ] stop ] end ;; Motes in the BNDY state detecting a change in their sensed value will set their rid to ;; zero and will transition to the IDLE state if none of their neighbors detect the to step_BNDY set color red if s_l != s [ ;; When sensed value changes set s_l s broadcast (list "upd8" who s) ;; Broadcast sensed value and identifier if length filter [item 1 ? = 0] d = count my-links [ ;; All neighbors sense value 0 type "Region disappeared at mote " type who type ". Rid: " type rid type "\n" ;; Report that region has disappeared ] become "IDLE" set rid 0 ;; Delete stored region id rid stop ] PNCH-BNDY ;; Runs the functions common to both the PNCH and BNDY states. end ;; Motes in the PNCH state detecting a change in their sensed value will transition to ;; the IDLE state and send messages with new rids to neighbors indicating that a split ;; has occurred. to step_PNCH set color yellow if s_l != s [ set s_l s broadcast (list "upd8" who s) ;; Broadcast sensed value and identifier become "IDLE" type "Region split at mote " type who type "." type "\n" ;; Report region r split let c_i CI foreach c_i [ let new_rid id_func (cyc ?) send (list "regn" new_rid who) (mote (cyc ?)) ;; Update rid for all boundary nodes ] set rid 0 stop ] PNCH-BNDY ;; Runs the functions common to both the PNCH and BNDY states. end ;; Motes receiving the upd8 message update their d table with the latest sensed value and ;; depending on the number of sequences of neighbors which are not part of the region, ;; will transition into either the IDLE, BNDY or PNCH state. ;; Motes receiving the regn message will update their rid value if the sent value is ;; different and forward this message to the neighboring boundary motes. ;; Motes receiving the idnt message will send their rid back to the mote which made the ;; request. to PNCH-BNDY if has-message "upd8" [ let msg received "upd8" let i' item 1 msg let s' item 2 msg let NewRecord (list i' s') let OldRecord first filter [item 0 ? = i'] d ;; Find record where i = i' set d replace-item (position OldRecord d) d NewRecord ;; set d(i') as s let c_i CI ;; IDs of neighbors n where d(n)=0 and d(cyc(n))=1 if length filter [item 1 ? = 1] d = count my-links [ become "IDLE" set rid 0 ] if length c_i = 1 [become "BNDY"] ;; Pinch point now in region interior if length c_i = 2 [become "PNCH"] ;; Boundary node now pinch point stop ] if has-message "regn" [ ;; Received regn message let msg received "regn" let r' item 1 msg if r' != rid [ ;; Region update message continues only as far as new updates required set rid r' let c_i CI foreach c_i [ send (list "regn" r' who) (mote (cyc ?)) ;; Update rid for all boundary nodes ] ] stop ] if has-message "idnt" [ ;; Received idnt message let msg received "idnt" let i' item 1 msg send (list "regn" rid who) (mote i') ;; Send rid to mote which made the idnt request stop ] end ;; Changing the labels of the motes based on the MoteLabel dropdown list to mote_labels ask motes [ if MoteLabel = "none" [set label ""] ;; Hide the label if MoteLabel = "mote id" [set label who] ;; Show mote id if MoteLabel = "sensed value" [set label s] ;; Show sensed value if MoteLabel = "region id" [ ;; Show non-zero region ids ifelse rid = 0 [set label ""] ;; Show nothing [set label rid] ;; Show region id ] ] end
The NetLogo procedures for this applet can be downloaded directly as: Protocol6.9.nlogo
All the NetLogo simulation models for this book depend on two library files: gsn.nls and env.nls
These files should be placed in the parent directory of the .nlogo file (and are common to all the .nlogo models on this website).