Decentralized Movement Analysis - Computational Movement Analysis - page 64

The decentralized algorithms for monitoring movement involves two stages—first
maintaining and exchanging records about movement events at cordons or fish, and
second querying these records. The paper presents a family of algorithms increasingly
relaxing constraints about the communication network. Whereas first all cordons
are connected, this assumption is relaxed as fish act as data mules to physically
move information in absence of other communication links. This is shown in Fig. 4.2
where fish 6 carries information about fish 5 back to node 101 from t 3 to t 4 .The
principle of exploiting the movement of objects to move around information is termed
mobility diffusion and will further be investigated in Sect. 4.3.2.2 . The final stage (not
depicted in Fig. 4.2 ) investigates what happens when fish passing one another hand
over information tokens. All three algorithms are summarized in Table 4.2 .
The algorithms were evaluated with respect to scalability and latency , that is the
delay between an event occurring and the event being detected correctly by the algo-
rithm. Latency is another decentralized spatial computing principle further explored
in Sect. 4.3.3.3 . All experiments were carried out with simulated moving objects
in the agent-based modeling environment NetLogo (Wilensky 1999 ). Both et al.
( P19 . 2013 ) summarize the results as follows. Algorithms 1 and 2 scale linearly with
the total number of fish. Equally expected, Algorithm 3 lends towards a commu-
nication complexity that scales with the square of the number of fish. Algorithm 1
performs best in terms of scalability and latency. Using data mules, Algorithm 2
achieves comparable computational efficiency, but at the cost of increased latency.
Finally, Algorithm 3 can further reduce the latency of Algorithm 2, but for the cost
of increased computational complexity (Table 4.3 ).
The structures presented in Both et al. ( P19 . 2013 ) also support algorithms for
queries of variable complexity. The complexity of the queries depends on the required
degree of coordination between the cordons. Whereas queries about the identity of
individual fish on an edge or total edge load at a given time can be handled by
individual cordons, queries about composite fish paths and collective movement of
fish (akin to flocking patterns) require cordon collaboration. Collaboration will be
further explored in Sect. 4.3.3.1 .

Table 4.2 Three different decentralized algorithms monitoring movement in a cordon structured
network in Both et al. ( P19 . 2013 )
Algorithm description DeSC peculiarities

Algorithm 1 Basic algorithm where all cordons are

directly connected in the
communication network to cordon
neighbors in the transportation graph

Best performance in terms of
scalability and latency

Algorithm 2 Mule algorithm, where fish transport

exit records back to cordons, Fig. 4.2

Mules compensate for
disconnected cordons, but at
cost of increased latency

Algorithm 3 Extended mule algorithm, where fish

transport and exchange exit records

Handshakes decrease latency at
cost of increased overall
computational complexity