Search Algorithms for Routing Adaptation (SARA): From Tabu Search Foundations (1994) to Statistically-Assisted and Energy-Aware Intelligence for Ad Hoc and Ubiquitous Computing

Abstract

Context: The acronym SARA has been used for at least four independent routing-related concepts, leading to conflation in manuscripts that present Tabu-based routing (1994) and Statistically Assisted Routing (2008) as a single lineage. Objective: This paper 1) distinguishes two SARA definitions with documented evidence, 2) identifies where SARA is only acronym overlap, 3) provides verified references for all claims, 4) corrects figure caption vs plotted-point inconsistencies and unsupported statistical claims, and 5) supplies a complete reproducibility specification satisfying IJCNS requirements. Methods: Distinction of Tabu-SARA (Search Algorithms for Routing Adaptation, 1994 claim, tabu list, tenure, aspiration) vs Rossi-SARA (Statistically Assisted Routing Algorithms, Rossi, Zorzi, Rao, Wireless Networks 14: 55-70, 2008) vs EASARA (Energy Aware Simple Ant Routing Algorithm, Jabbar et al. 2015) vs Simple Ant SARA (MANET). Full reproducibility spec: ns-3.36, YansWifiPhy LogDistance + LogNormal σ4dB, AdhocWifiMac GeRaF 4 regions, BasicEnergySource 2J, 500 × 500 uniform placement ≥ 95% connectivity, 10% independent duty-cycle, N-1 CBR, 300 s duration, 6 densities × 10 seeds = 300 runs, static ConstantPosition, metrics with CI and t-test. Results: Corrected visual estimates 50 nodes EASARA ~215 SARA ~174 MFR ~112 (not 220/180/120); 200 nodes MFR ~90 SARA ~156 Tabu ~162 EASARA ~200 (not 95/155). Corrected rising curves offline optimal 1.00 → 1.05, SARA 1.11 → 1.20, MFR 1.28 → 1.38 (not flat 1.10× within 10% at all distances, 14.3% over at 10 hops). Tabu parameters tenure 7 - 12, aspiration 5%, loop reduction 73%, hybrid +8% audited as DESIGN CHOICE/HYPOTHESIS. Conclusion: No citation chain Tabu-SARA → Rossi-SARA. Acronym identity is coincidental reuse. Contribution is distinction with verified references, corrected figures/tables, full statistical reproducibility spec, and novel synthesis proposal labeled as new hypothesis.

Share and Cite:

AlMahmeed, A. (2026) Search Algorithms for Routing Adaptation (SARA): From Tabu Search Foundations (1994) to Statistically-Assisted and Energy-Aware Intelligence for Ad Hoc and Ubiquitous Computing. International Journal of Communications, Network and System Sciences, 19, 113-127. doi: 10.4236/ijcns.2026.198008.

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.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1] Rossi, M., Zorzi, M. and Rao, R.R. (2006) Statistically Assisted Routing Algorithms (SARA) for Hop Count Based Forwarding in Wireless Sensor Networks. Wireless Networks, 14, 55-70.[CrossRef]
[2] Johnson, D.B. and Maltz, D.A. (1996) Dynamic Source Routing in ad Hoc Wireless Networks. In: Imielinski, T. and Korth, H.F., Eds., Mobile Computing, 153-181.
[3] Perkins, C.E., Belding-Royer, E.M. and Das, S.R. (1999) Ad-Hoc On-Demand Distance Vector Routing. Second IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, 25-26 February 1999, 90-100.
[4] AlMahmeed, A.S. (1994) SARA Adaptive Routing Using Tabu Search. Ph.D. Thesis, University of Strathclyde, Glasgow.
[5] Rossi, M., Zorzi, M. and Rao, R.R. (2008) Statistically Assisted Routing Algorithms (SARA) for Hop Count Based Forwarding in Wireless Sensor Networks. Wireless Networks, 14, 55-70.
http://www.dei.unipd.it/~rossi/papers/RossiWirelessNets2008.pdf
[6] Jabbar, S., Iram, R., Imran, M., Ahmad, A., Paul, A., Minhas, A.A., et al. (2015) Energy Aware Simple Ant Routing Algorithm for Wireless Sensor Networks. Mathematical Problems in Engineering, 2015, Article ID: 194532.[CrossRef]
[7] Glover, F. (1986) Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research, 13, 533-549.[CrossRef]
[8] Zorzi, M. and Rao, R.R. (2003) Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance. IEEE Transactions on Mobile Computing, 2, 349-365.[CrossRef]
[9] Koenig, S., Likhachev, M. and Lite, D. (2002) Proceedings of the AAAI Conference on Artificial Intelligence, Edmonton, 476-483.
[10] Bond, D., Widger, N., Ruml, W. and Sun, X. (2010) Real-Time Search in Dynamic Worlds. Proceedings of the International Symposium on Combinatorial Search, 1, 16-22.[CrossRef]
[11] Kleinrock, L. and Silvester, J.A. (1978) Optimum Transmission Radii for Packet Radio Networks, or Why Six Is a Magic Number. Proceedings of the IEEE National Telecommunications Conference, 4, 1-4.
[12] Li, X., Lee, J., et al. (2024) Comprehensive Comparative Study of State-of-the-Art Path-Planning. Applied Sciences, 15, 148.

Copyright © 2026 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.