Search Algorithms for Routing Adaptation (SARA): From Tabu Search Foundations (1994) to Statistically-Assisted and Energy-Aware Intelligence for Ad Hoc and Ubiquitous Computing ()
1. Introduction
1.1. Motivation and Problem Statement
Routing in duty-cycled wireless sensor networks (WSNs) must minimize hop count, maximize residual energy, avoid congestion, and operate with minimal control overhead [1]. Conventional ad hoc protocols such as DSR [2] and AODV [3] could fail to discover complete paths or fail to converge when radios are periodically switched off to save energy [1]. A commonly accepted approach is to periodically switch off radio of some nodes and to not account for routing tables at all, as a generic sensor node only needs to know which is the best node to be selected as relay for current transmission [1].
The literature contains multiple independent proposals using the acronym SARA, which has caused conflation. This paper addresses IJCNS reviewer concerns that prior version presented Tabu-based routing (1994) and Rossi et al. statistically assisted routing (2008) as one direct lineage without documented technical or terminological evidence.
1.2. Acronym Overload—Why SARA Alone Does Not Establish
Lineage
Search reveals at least four independent SARA expansions:
SARA (1994 claim) = Search Algorithms for Routing Adaptation (Tabu-based, packet-switched, author thesis [4])
SARA (2008) = Statistically Assisted Routing Algorithms (Rossi et al., WSN hop-count forwarding) [1] [5]
SARA (MANET) = Simple Ant Routing Algorithm (low-overhead ant-based MANET protocol, base for EASARA) [6]
SARA (2024) = Singular-Value Based Adaptive Low-Rank Adaptation (He et al., LLM fine-tuning)
EASARA (2015) = Energy Aware Simple Ant Routing Algorithm [6] explicitly builds on Simple Ant SARA, not Rossi SARA.
Jabbar et al. verification: “To cope with limited energy problem, we present EASARA, an energy aware simple ant routing algorithm based on ant colony optimization. Unlike most algorithms, EASARA strives to avoid low energy routes and optimizes the routing process through selection of least hop count path with more energy.” and “SARA uses the hop distance, and the pheromone value as metrics whereas EASARA introduces another metric... node energy and number of hops.” Therefore acronym identity is insufficient evidence of technical continuity.
1.3. Contributions
C1: Clear distinction between Tabu-SARA and Rossi-SARA with documented definitions, technical/terminological/citation divergence.
C2: Identification of where SARA is only acronym overlap, with verified sources.
C3: Full reproducibility specification: MAC/PHY, energy, placement, duty-cycle, source count, runs/topologies, seeds, duration, mobility, uncertainty intervals, hypothesis tests.
C4: Clarification of comparable vs external baselines (D* Lite, RTD* requires global graph state, presented as external upper bounds).
C5: Audit of tabu parameters (tenure, aspiration, loop reduction 73%, Tabu-EASARA +8%) with design choice vs hypothesis labeling and verification experiments.
C6: Correction of figure caption vs plotted-point inconsistencies (10×, rises 1.11 → 1.20 vs optimal 1.00 → 1.05, exceeds 10% claim).
C7: Restructured paper with verified references for IJCNS final submission.
2. Related Work—Verified References Only
2.1. Tabu Search for Routing (1994 Claim) [4] [7]
Glover 1986 introduces Tabu Search using short-term and long-term adaptive memory to forbid revisiting recently explored attributes to escape local minima. AlMahmeed Ph.D. thesis (claimed July 1994, University of Strathclyde) [4] reports application to adaptive routing: routing solution is a path, neighbourhood defined by swapping next-hop, tabu list per destination prevents revisiting recently explored next-hops, aspiration allows tabu move if improves best cost. No independent bibliographic record found in public thesis database for exact title; no page numbers for tenure 7 - 12, tenure 10, sqrt (|S|), aspiration 5%, loop reduction 73% provided. Therefore treated as distinct proposal by author, not cited foundation of Rossi. Classification: design choices/hypotheses pending verification (Section 5.9).
2.2. Statistically Assisted Routing Algorithms (Rossi et al. 2008)
[1] [5] [8]
Rossi, Zorzi, Rao, Wireless Networks 14: 55-70, 2008, DOI 10.1007/s11276-006-7791-8, online 9 June 2006 [1]. Full PDF [5] defines SARA as family where path selection is accomplished through hop-by-hop forwarding accounting for state within transmission range and statistically accounting for state outside coverage area. Forwarding decisions are driven by statistical information on costs within coverage and in second-order neighborhood. Each node knows own cost and hop count HC (minimum hop path). Cost c_ij = f (Ps_ij, Eres_j, a_j) where Ps is packet reception rate, Eres normalized residual energy, a_j normalized advancement. By analysis proves optimal online stationary policy exists, derives its form, exploits as core of SARA. Exploitation of second order substantially increases goodness vs fully localized greedy routing [1]. For neighbor discovery uses Geographic Random Forwarding (GeRaF) [8] Zorzi & Rao IEEE TMC 2: 349-365, 2003: node activity follows random sleep schedule to conserve energy, source broadcasts, if multiple nodes pick closest to destination, otherwise reattempt later, cross-layer MAC/routing. No tabu mechanism in Rossi.
2.3. Energy Aware Simple Ant Routing Algorithm (EASARA) [6]
Jabbar et al., Mathematical Problems in Engineering, vol.2015, Article ID 194532, 2015 [6]. Verified statements: To cope with limited energy problem, we present EASARA, an energy aware simple ant routing algorithm based on ant colony optimization. Unlike most algorithms, EASARA strives to avoid low energy routes and optimizes routing through selection of least hop count path with more energy. SARA uses hop distance and pheromone value as metrics whereas EASARA introduces node energy and number of hops. Employs Controlled Neighbor Broadcast (CNB) where one neighbor only broadcasts FANT further, overhead O (1) vs O (|S|). Forwarding four cases: high energy + low hops p = 0.8, high + high p = 0.5, low + low p = 0.2, low + high p = 0.05. Pheromone update tau_ij = (1 − ρ) tau_ij + Δ, Δ = Q*E_min/hops, evaporation ρ 0.2 - 0.3 tuned. This SARA refers to Simple Ant Routing Algorithm (MANET), not Rossi.
2.4. Incremental and Real-Time Search—External Comparisons
[9] [10]
D* Lite [9] Koenig & Likhachev AAAI 2002 pp. 476-483: D* Lite recasts dynamic replanning into simpler incremental heuristic-search structure with formal guarantees, implements same behavior as Stentz Focused Dynamic A* but algorithmically different, avoids reordering priority queue vs LPA*, efficiency ≥ D* with lower memory, O (k log k) incremental by updating only affected regions. Li et al. 2024: D* Lite significantly reduces replanning time by updating only affected regions instead of recomputing complete path. RTD* [10] Bond et al. SOCS 2010: Existing dynamic search such as D* Lite are not real-time. RTD* combines LSS-LRTA* lookahead from agent to goal while D* Lite runs reverse from goal, sharing heuristic via bidirectional search, producing first real-time search algorithm designed for dynamic worlds, results in significantly shorter trajectories than either LSS-LRTA* or naive real-time adaptations of D* Lite because of ability to opportunistically exploit shortcuts. Both require global graph state.
3. Distinction Framework—Evidence That Establishes
Relationship vs Acronym Overlap
Terminological evidence: Tabu-SARA expansion = Search Algorithms for Routing Adaptation (1994 claim). Rossi-SARA expansion = Statistically Assisted Routing Algorithms (2008 documented). Expansions differ, both yield letters S-A-R-A but definitions distinct.
Technical evidence: Tabu-SARA mechanism = tabu list per destination tenure 7 - 12, aspiration 5%, neighborhood swapping next-hop, loop avoidance. Rossi-SARA mechanism = second-order histogram H_j of min c_jk, GeRaF contention, Bellman optimality E_{S_i}[min_j (c_ij + V_j)] threshold policy, no tabu list. No overlap in pseudocode.
Citation evidence: Rossi et al. 2008 reference list contains no AlMahmeed 1994. Web search for AlMahmeed PhD 1994 Strathclyde SARA returns no independent record outside this manuscript. Therefore direct lineage cannot be established by documented evidence. Relationship must be presented as novel synthesis, not historical evolution.
Acronym overlap evidence: Simple Ant Routing Algorithm (MANET) also abbreviated SARA, base for EASARA per Jabbar. Singular-Value Adaptive Low-Rank Adaptation (2024) also SARA. Acronym reuse is common; identity alone does not imply technical lineage.
4. Proposed Methodology—Novel Synthesis (Not Historical
Lineage)
4.1. System Model (Follows Rossi)
Graph G(t) = (V, E(t)). Neighbor set S_i(t) random due to duty cycling. HC_i shortest hop distance to sink via limited flood. Eres_i in [0, 1], Ps_ij packet reception rate. Edge cost c_ij(t) = α(1 − Ps_ij) + β(1 − Eres_j) + γ(1 − a_j) where a_j normalized advancement. Second-order: node i maintains histogram H_j of M_j = min_{k∈S_j} c_jk reported by neighbor j. Objective J = E[Σc]. Bellman: V_sink = 0, V_i = E_{S_i}[min_{j∈S_i}(c_ij + V_j)]. Under i.i.d. costs stationary threshold policy (Rossi proof).
4.2. Algorithms Sharing Identical ns-3 Information and
Communication Assumptions (Group A—Directly Comparable)
Same stack per Sec 5: YansWifiPhy LogDistance+LogNormal σ4dB, AdhocWifiMac GeRaF 4 regions, 10% independent duty-cycle 100 ms/900ms, placement 500 × 500 acceptance ≥ 95% connectivity, 2J energy, N-1 sources.
1) MFR: advancement only, S_i via probe, no cost, no second-order, no tabu, no pheromone.
2) Rossi SARA: c_ij, HC_j via 30 s flood, H_j histogram EWMA α0.3 mean*0.9 optimism, score = c_ij + E[Cost|HC_j].
3) Tabu-SARA: Same as Rossi + tabu list T per destination DESIGN CHOICE tenure 10 (range 7 - 12 heuristic from Glover), N(i) = {j∉T or aspiration DESIGN CHOICE 5% improvement}. This is author’s 1994 mechanism, not part of Rossi.
4) EASARA: Simple Ant base, Eres, hops, pheromone tau, CNB one neighbor rebroadcasts FANT, four-case p = 0.8/0.5/0.2/0.05, ρ = 0.25, quality = minEnergy/max_hops*1/hops*pheromone [11].
4.3. Algorithms Requiring Global Graph State—External
Comparisons (Group B—Not Directly Equivalent)
D* Lite and RTD* cannot operate under same local, routing-table-free, duty-cycle-aware assumptions. D* Lite assumes agent maintains full graph G and receives exact edge cost changes. Incremental replanning O (k log k) by updating only inconsistent nodes g ≠ rhs, priority queue [min (g, rhs) + h + km, min (g, rhs)]. To obtain global state in WSN would require all-awake flooding O (V + E) per update violating Rossi premise to periodically switch off radio and not account for routing tables. In manuscript implemented as offline oracle: freeze duty-cycle (all awake), extract full graph, compute Dijkstra 1.00x lower bound. Therefore D* Lite results (normalized replanning 8 vs Dijkstra 100, 92% reduction) are B-Synthesis from Koenig & Li et al., not same-stack measurement. RTD* similarly requires forward LSS-LRTA* + reverse D* Lite costs outside coverage, needs continuous sink-to-all flooding. Its result 18% shorter than LSS-LRTA* is B-Synthesis from Bond et al. Both must be labeled “External upper bound—requires global graph state, O (V) memory, not duty-cycle constrained” in figures, dashed lines separate from solid Group A.
4.4. Novel Hybrid Hypothesis
Hybrid Tabu-Statistical SARA: Rossi score c_ij + E_j filtered by tabu list to avoid flapping and recently failed nodes. Tabu prevents ant revisiting recently failed nodes, pheromone guides exploitation. Hypothesized +8% lifetime over pure EASARA based on illustrative run, no replicated log-labeled hypothesis for future work requiring experiment Section 5.9. Explicitly NOT claimed as previously published or part of Rossi.
5. Reproducibility and Statistical Specification
5.1. Provenance Taxonomy
A = ORIGINAL ns-3 OUTPUT requires ns-3 version + commit, seed list, raw logs (.tr, energy trace, decision log), mean ± stdev 95% CI n = 10, hypothesis tests. B = SYNTHESIS FROM CITED LITERATURE paraphrases peer-reviewed results (Rossi substantially increases goodness, Jabbar avoids low energy routes, Koenig D* Lite avoids reordering, Bond RTD* first real-time). C = ILLUSTRATIVE EXAMPLE hypothetical constants (25%, 40%, 1.35x, 1.10x flat, 220/180/120, 95/155, 82%/94%/96%, tenure 7 - 12, sqrt (|S|), aspiration 5%, loop reduction 73%, hybrid +8%). All numbers in current draft are B or C until logs deposited. Previous version presented B/C as A—corrected per reviewer.
5.2. MAC/PHY Models
PHY YansWifiPhy LogDistance exponent 3.0 ref 46.67dB@1m + LogNormalShadowing sigma 4 dB → PRR 0.7 - 0.95, Tx 0dBm, Rx sensitivity −92 dBm, Noise 7 dB, 2.4 GHz 2 MHz 250 kbps (Wifi) or 1 Mbps. Alternative LrWpanSpectrumModel 802.15.4 250kbps. MAC AdhocWifiMac GeRaF 4 priority regions by advancement a_j, CWmin7 CWmax255 slot20us SIFS10us DIFS50us, no RTS/CTS, probabilistic channel contention per Zorzi & Rao 2003. Baseline 802.15.4 LrWpanMac unslotted CSMA BE 3-5. Channel single.
5.3. Energy Model
BasicEnergySource 2 J per node, sink unlimited, Volt 3.0 V. WifiRadioEnergyModel/LrWpanRadioEnergyModel CC2420: Tx 17.4 mA, Rx 19.7 mA, Sleep 0.02 mA, Idle 0.02 mA → 0.05 J Tx, 0.02 J Rx per 64 B packet. Accounting interval 1 s, depletion callback node death. Energy trace every 10 s.
5.4. Placement and Topology Acceptance
Deployment static ConstantPositionMobilityModel (main) to match Rossi. Uniform random 500 × 500 m, sink (0, 0). Acceptance criterion: BFS from sink under full awake median path loss 50 m range requires ≥ 95% nodes have path to sink (intermittently connected but underlying connected). If not, resample. Save positions_density_D_seed_S.txt. Optional mobile extension RandomWaypoint 5 - 15 m/s pause0 s 500 × 500 for FANET mapping—separate experiment labeled mobile, not same as static Rossi assumptions.
5.5. Duty-Cycle Schedule
10% independent per node (Rossi model): period 1 s = 100 ms active/900ms sleep, phase offset uniform [0, 1) s per node at t = 0. During sleep radio SLEEP state not reachable, S_i(t) random. Implements Rossi random S_i due to duty cycling. HC refresh limited flood from sink every 30 s when nodes awake, nodes buffer flood if asleep until next wake. EWMA α = 0.3 for second-order histogram 20 samples per direction (80 bytes/dir).
5.6. Traffic and Source Count
Sources: All non-sink nodes N-1 (49 to 299) CBR 1 pkt/s/node 64 B payload +12 B SARA header (HC, Eres, hist) UDP TTL32, jitter uniform [0, 1) s to avoid sync. Total offered load 49 - 299 pkt/s. Alternative 20% random subset seed-controlled for scalability study—must be stated if used. Simulation duration 300 s simulated time, warm-up 0 - 30 s excluded from metrics.
5.7. Runs, Topologies, Seeds, Duration
Densities 50, 100, 150, 200, 250, 300 (6 levels). Topologies per density 10 independent placements seeds 1 - 10. Total topologies 60. Runs per topology per algorithm 1 (deterministic given seed). Total runs 60 × 5 (MFR, Rossi SARA, Tabu-SARA, EASARA, D* Lite offline oracle) = 300 runs. Seeds RngSeedManager RngSeed 1 - 10 RngRun1 controlling placement, shadowing, PRR, duty-cycle offset, traffic jitter, backoff. Duration 300 s sim, warm-up excluded. Logs: positions, energy trace, .tr, pcap at sink, SARA decision log (next-hop, c_ij, E_j, tabu status). Deposit Zenodo DOI required to claim A.
5.8. Metrics, Uncertainty Intervals, Hypothesis Tests
PDR = delivered_at_sink/generated_in_window (30 - 300 s) per seed → mean ± stdev 95% CI mean ± 1.96*stdev/√10 n = 10. Example format: SARA PDR 94.1% ± 1.1% CI 93.4% - 94.8% n = 10.
Lifetime = time until first partition (<50% nodes have awake-path to sink) → rounds = time/1s, mean ± stdev CI. Example EASARA 198.3±12.4 CI 190.6 - 206.0 vs SARA 155.7 ± 10.2 CI 149.4 - 162.0.
Path-cost normalized = actual Σc_ij/offline optimal Σc_ij on full-awake snapshot at packet generation → average per run per hop bin 2 - 4, 5 - 7, 8 - 10 hops to avoid flat mischaracterization. Report mean ± stdev CI per bin. Previous single-point 1.35×/1.10× flat withdrawn.
Hypothesis tests: paired t-test by topology seed (same placement) for each density SARA vs MFR etc., null H0 mean diff = 0, α = 0.05, report t (9), p, Cohen d. ANOVA across algorithms per density + Tukey HSD. For path-cost vs distance repeated measures ANOVA hop bin within factor. Without these, differences 25%/40%/73%/8% cannot be statistically assessed.
5.9. Audit of Tabu Parameters—Design Choice vs Hypothesis
Tenure 7 - 12, 10, sqrt (|S|): Rossi 0 hits for tabu, Jabbar 0 hits, Glover 1986 says 7 - 20 typical for TSP no WSN sqrt, no thesis page provided → DESIGN CHOICE: tenure 10 chosen for illustration within 7 - 12 heuristic, sqrt (|S|) hypothesis.
Aspiration 5%: Rossi none, EASARA none, Glover generic no 5% for routing → DESIGN CHOICE: aspiration 5% improvement heuristic, no sensitivity.
Loop reduction 73% vs DV: Sec 9 claims thesis showed 73% but no page/figure/table, no log, no citation in Rossi/Jabbar/Koenig → UNVERIFIED HYPOTHESIS (author-reported) must be “Hypothesis (claimed in 1994 thesis, page TO BE INSERTED): 73% loop reduction vs DV under conditions TO BE INSERTED, no log deposited.”
Tabu-EASARA +8% lifetime: no log, Jabbar/Rossi do not contain hybrid → HYPOTHESIS/ILLUSTRATIVE: hybrid tabu avoids failed nodes hypothesized +8% lifetime illustrative run.
Experiments to verify: tenure sweep {5, 7, 10, 12, 15, 20, sqrt (|S|), |S|/2} metric loops/1000 pkts; aspiration sweep {0%, 1%, 5%, 10%, 20%} metric PDR/path-cost; DV baseline Bellman-Ford same duty-cycle vs Tabu tenure10 count cycles (loops_DV-loops_Tabu)/loops_DV; EASARA vs EASARA + tabu lifetime mean ± stdev t-test. Until then prefix Design choice: or Hypothesis.
5.10. Figure Caption vs Plot Inconsistencies—Corrected
Previous captions reported inconsistent values versus plotted points (e.g., 50 nodes 220/180/120 vs ~215/174/112; 200 nodes 95/155 vs ~90/156; SARA 1.10× flat within 10% vs rising 1.11 → 1.20). All inconsistent captions have been corrected and labeled [C] illustrative. Corrected visual estimates are provided in Figures 1-3 below.
6. Results and Discussion [All Values Illustrative/Synthesis
until Logs Deposited—See Sec 5]
Figure 1 [C—Illustrative, not original ns-3 output]: Lifetime rounds until first partition vs density. Corrected visual estimates: 50 nodes EASARA ~215 rounds, Rossi SARA ~174 rounds, MFR ~112 rounds (not 220/180/120); 200 nodes MFR ~90 rounds, Rossi SARA ~156 rounds, Tabu-SARA ~162 rounds, EASARA ~200 rounds (not 95/155). Previous caption inconsistent—corrected. Trend illustrates Jabbar et al. [6] lifetime increases with choices enabling balancing, prolongs lifetime. Requires seeds 1 - 10 logs to claim A. See Figure 1.
Figure 1. Network lifetime vs density [C—Illustrative, Corrected].
Figure 2 [C—Illustrative, synthesis from Rossi [1] [5]]: Normalized cost vs hops. Visual: offline optimal 1.00 → 1.05, SARA 1.11 → 1.20, MFR 1.28 → 1.38. Previous claimed SARA 1.10× flat within 10% at all distances inaccurate—withdrawn. At 10 hops 1.20 vs 1.05 = 14.3% over optimal, exceeding 10% claim. Illustrates Rossi [1] substantially increases goodness vs fully localized greedy, but not flat. See Figure 2.
Figure 2. Path cost vs distance [C—Illustrative, Synthesis].
Figure 3. Replanning cost comparison [B—Synthesis].
Figure 3 [B—Synthesis from Koenig [9] + Li et al. [12]]: Relative replanning time normalized Dijkstra 100 (ref), A* 35 illustrative, D* Lite 8 B-Synthesis from Koenig & Li et al. significantly reduces time by updating only affected regions, Rossi SARA per-hop 2 no global recompute. D* Lite avoids reordering priority queue, efficiency ≥ D* with lower memory [9]. See Figure 3.
Tables—Sequentially Numbered and Cited in Numerical Order
Table 1 summarizes complexity of algorithms with verified sources. Complexity details are shown in Table 1 [1] [4] [6] [7] [9] [12].
Table 1. Complexity analysis—verified sources.
Algorithm |
Complexity (verified) |
Memory |
Optimality |
Source |
Tabu-SARA
1994 claim |
O (|S| log |S|) + tabu O
(tenure) DESIGN CHOICE |
O (|S|) + tabu + hist |
Metaheuristic hypothesis |
Author [4],
Glover 1986 [7] |
Dijkstra binary heap |
O ((V + E) logV) |
O (V) |
Optimal |
Standard |
A* consistent h |
O (b^d) worst << Dijkstra |
O (b^d) |
Optimal if admissible |
Standard |
D* Lite |
O (k log k) incremental,
avoids reordering vs LPA* |
O (V) |
Optimal, ≥ D* |
[9] [12] |
Rossi SARA |
O (|S| log |S|) per hop,
no table |
O (|S|) + hist 80B/dir |
Statistically optimal online,
illustr. ~1.11 - 1.20× |
[1] [5] |
EASARA |
O (|S|) + ants |
O (|S|) pheromone |
Energy-balanced,
prolongs lifetime |
[6] |
Table 2 provides full reproducibility specification required for IJCNS. Simulation parameters are detailed in Table 2 [8].
Table 2. Simulation parameters—full reproducibility spec.
Parameter |
Value (Required for A) |
Simulator |
ns-3.36 commit [INSERT], repo [INSERT DOI] |
Area |
500 × 500 m sink (0, 0) |
Densities |
50, 100, 150, 200, 250, 300 |
Topologies
per density |
10 seeds 1 - 10 acceptance ≥95% connectivity |
Total runs |
300 (60 topologies ×5 algos) |
Duration |
300 s sim, warm-up 0 - 30 s excluded |
Mobility |
ConstantPosition static (main), RandomWaypoint 5 - 15 m/s optional |
Sources |
N-1 (49 - 299) CBR 1 pkt/s 64 B + 12 B jitter U [0, 1) s TTL32 |
PHY |
YansWifiPhy LogDistance exp3 ref46.67dB + LogNormal σ4dB PRR0.7 - 0.95
Tx0dBm Rx-92dBm |
MAC |
AdhocWifiMac GeRaF 4 regions by a_j CWmin7 CWmax255 no RTS/CTS [8] |
Duty-cycle |
10% independent 100 ms/900ms period 1 s offset U [0, 1) s |
Energy |
BasicEnergySource 2 J CC2420 Tx 17.4 mA Rx 19.7 mA Sleep 0.02 mA |
Seeds |
RngSeed1 - 10 RngRun1 controls placement/shadowing/PRR/offset/jitter/backoff |
Metrics |
PDR, lifetime rounds, normalized cost, msgs/hop mean ± stdev 95% CI n = 10
paired t-test ANOVA |
Table 3 audits previously unsupported claims relabeled as DESIGN CHOICE/HYPOTHESIS. Audit details are summarized in Table 3. See Table 3.
Table 3. Audit of unsupported claims—relabeled.
Claim |
Previous |
Correct framing |
Experiment required |
Tenure 7 - 12, 10, sqrt (|S|) |
tenure 7 - 12 sqrt (|S|) works well |
DESIGN CHOICE tenure10 heuristic |
Sweep {5, 7, 10, 12, 15, 20,
sqrt} loops/1000 pkts |
Aspiration 5% |
aspiration > 5% |
DESIGN CHOICE 5% heuristic |
Sweep {0%, 1%, 5%, 10%,
20%} PDR |
Loop reduction 73% |
reduces loops 73%
vs DV |
HYPOTHESIS author-reported
unverified |
DV baseline same
duty-cycle count cycles |
Tabu-EASARA +8% |
improves 8% over EASARA |
HYPOTHESIS illustrative |
EASARA vs + tabu
lifetime t-test |
25% over MFR, within10% optimal |
25% over MFR within10% optimal |
B Synthesis 25%/10% illustrative
quantifications of Rossi qualitative [1] |
Mean ± CI per hop bin |
40% over SARA |
40% over SARA |
B Synthesis 40% illustrative constant of Jabbar trend [6] |
Lifetime mean ± CI |
Table 4. SARA variants across domains—acronym overlap.
Domain |
Variant |
Core |
Source |
Overlap Note |
Origin 1994
claim |
Tabu-SARA |
Tabu tenure DESIGN CHOICE |
Author [4] |
Search Algorithms—distinct
expansion |
WSN 2008 |
Rossi SARA |
Second-order stats,
c_ij = f (Ps, Eres, a) |
Rossi 14:55-70
[1] [5] |
Statistically Assisted—distinct,
no tabu |
WSN 2015 |
EASARA |
Avoid low energy, least hop
with more energy, CNB |
Jabbar Art194532
[6] |
Energy Aware Simple Ant—builds
on Simple Ant MANET, not Rossi |
MANET |
Simple Ant
SARA |
Ant hop + pheromone |
Literature |
Third expansion |
Real-time |
RTD* |
First real-time for dynamic,
shorter than LSS-LRTA* |
Bond SOCS
2010 [10] |
External requires global state |
Table 4 clarifies SARA variants across domains and acronym overlap. Variant details are presented in Table 4. Details in Table 4.
7. Discussion
7.1. Acronym Overload and Citation Integrity
Acronym overload is common in networking: our audit confirms SARA has been used for at least four independent concepts (Table 4): 1) Search Algorithms for Routing Adaptation (Tabu-based, 1994 claim, packet-switched, author-reported) [4] [7], 2) Statistically Assisted Routing Algorithms (Rossi et al. 2008, WSN hop-count forwarding accounting for state within range and statistically outside coverage [1] [5]), 3) Simple Ant Routing Algorithm (MANET base for EASARA) [6], and 4) Singular-Value Low-Rank Adaptation (2024). Acronym identity alone does not establish technical lineage. Our terminological evidence shows different expansions, technical evidence shows tabu memory vs second-order histograms and GeRaF contention [8], and citation evidence shows Rossi [1] does not cite AlMahmeed 1994 [4], no independent bibliographic record outside manuscript, and Jabbar et al. [6] builds on Simple Ant MANET, not Rossi. No citation chain Tabu-SARA → Rossi-SARA → EASARA was found. D* Lite [9] and RTD* [10] cannot be evaluated under same local routing-table-free duty-cycled assumptions without centralized all-awake flooding O (V + E) violating Rossi premise [1]. They are therefore presented as external upper bounds (Figure 3) requiring global graph state.
7.2. Limitations
Current draft provides no deposited logs, no seed list, no confidence intervals, no hypothesis tests, therefore all numerical differences remain illustrative per provenance taxonomy A/B/C defined in Sec 5.1. Specifically: 1) The lifetime rounds and path cost values are visual estimates from plots (~215/174/112 at 50 nodes, ~90/156/200 at 200 nodes; 1.00 → 1.05 optimal, 1.11 → 1.20 SARA, 1.28 → 1.38 MFR) not mean ± stdev 95% CI across seeds 1 - 10; 2) Tabu parameters tenure 7 - 12, 10, sqrt (|S|), aspiration 5% are DESIGN CHOICE heuristics within Glover 7 - 20 typical for TSP [7], without ablation; loop reduction 73% and Tabu-EASARA +8% are HYPOTHESIS author-reported without page/table/log; 3) 25%/10%/40% gains are B-Synthesis illustrative quantifications of Rossi qualitative ‘substantially increases goodness vs fully localized greedy’ [1] and Jabbar trend [6]; 4) D* Lite O (k log k) 92% reduction is B-Synthesis from Koenig [9] and Li et al. [12]; 5) Mobility model for FANET mapping not yet evaluated under same stack. To claim ORIGINAL ns-3 OUTPUT, required per Sec 5.8: ns-3 version + commit, seed list 1 - 10, raw logs (.tr, energy trace, decision logs), positions files, mean ± stdev 95% CI mean ± 1.96*stdev/√10 n = 10, paired t-test by seed t (9) p Cohen d, ANOVA + Tukey, repeated measures per hop bin.
7.3. Future Work
Future work: 1) Implement Sec 5 full spec and deposit Zenodo DOI with positions_density_D_seed_S.txt, energy traces, .tr, decision logs, report revised parameters with mean ± stdev CI p-values; 2) Implement novel hybrid Tabu + Statistical SARA: Rossi score c_ij filtered by tabu list to avoid flapping and recent loops, with tabu tenure sweep {5, 7, 10, 12, 15, 20, sqrt (|S|)} metric loops/1000 pkts and aspiration sweep {0%, 1%, 5%, 10%, 20%} metric PDR/path-cost, EASARA vs EASARA + tabu lifetime mean ± stdev t-test; 3) Evaluate FANET RandomWaypoint 5 - 15 m/s under same stack as separate scenario; 4) Provide provenance labels [A] ORIGINAL, [B] SYNTHESIS, [C] ILLUSTRATIVE for every number in all tables and figures.
8. Conclusion
SARA has two independent origins: Search Algorithms for Routing Adaptation (Tabu-based, 1994 claim, author-reported) [4] [7] and Statistically Assisted Routing Algorithms (Rossi et al. 2008 documented as greedy forwarding driven by second-order cost statistics [1] [5]). EASARA builds on Simple Ant Routing Algorithm (MANET) per Jabbar [6]. Acronym identity is coincidental reuse. No documented citation chain establishes Tabu-SARA as foundational to Rossi-SARA. D* Lite [9] and RTD* [10] require global graph state and are external upper bounds (the corresponding figure). All figure caption vs plot inconsistencies corrected (values 220/180/120 vs ~215/174/112 at 50 nodes, 95/155 vs ~90/156 at 200 nodes; the corresponding figure not flat 1.10x but 1.11 → 1.20 vs optimal 1.00 → 1.05 exceeding 10% claim, 14.3% at 10 hops). Tabu parameters audited as design choices/hypotheses. Contribution is distinction with verified references [1]-[12], full reproducibility spec for IJCNS, corrected figures/tables (all tables and figures), and novel synthesis proposal labeled as new hypothesis, not historical lineage.