# Dynamic ASR pathways: An Adaptive Masking Approach towards efficient pruning
of a multilingual ASR model

###### Abstract

Neural network pruning offers an effective method for compressing a
multilingual automatic speech recognition (ASR) model with minimal performance
loss. However, it entails several rounds of pruning and re-training needed to
be run for each language. In this work, we propose the use of an adaptive
masking approach in two scenarios for pruning a multilingual ASR model
efficiently, each resulting in sparse monolingual models or a sparse
multilingual model (named as Dynamic ASR Pathways). Our approach dynamically
adapts the sub-network, avoiding premature decisions about a fixed sub-network
structure. We show that our approach outperforms existing pruning methods when
targeting sparse monolingual models. Further, we illustrate that Dynamic ASR
Pathways jointly discovers and trains better sub-networks (pathways) of a
single multilingual model by adapting from different sub-network
initializations, thereby reducing the need for language-specific pruning.

Index Terms—  Multilingual, Automatic Speech Recognition, Sparsity, Pruning

##  1 Introduction

Automatic speech recognition (ASR) has become a key feature in smart devices,
serving a diverse customer base [1, 2, 3]. For a successful on-device
deployment, the ASR model must operate within the storage and computational
constraints while delivering an optimal performance. Furthermore, the ASR
model needs to support multiple languages [4, 5] to interact with users
worldwide. Neural network pruning [6, 7, 8] is an effective technique for
reducing the size of an ASR model with minimal performance loss [9, 10].
However, the pruning process, such as Iterative Magnitude Pruning (IMP) [6,
11] and Lottery Ticket Hypothesis (LTH) [8], involves multiple iterations of
pruning and re-training to achieve the best performance. The pruning step
identifies a task-specific sub-network within the original dense neural
network. Subsequently, the re-training step trains this sub-network with task-
specific data, mitigating the performance loss introduced in pruning. This
iterative process continues until the target sparsity level is reached.

Pruning a multilingual ASR model presents specific challenges. When pruning a
pre-trained dense multilingual ASR model, it can result in two scenarios, as
discussed in [12]. In the first scenario, the model is fine-tuned and pruned
for each language separately, resulting in multiple language-specific sparse
models. While this approach optimizes performance in each language, it can
increase storage requirements due to maintaining different monolingual models.
In the second scenario, the multilingual model is fine-tuned and pruned using
a multilingual dataset, creating a single sparse model by finding a language-
agnostic pruning mask. While multilingual training can promote knowledge
transfer across languages [13, 14], data imbalance [15, 16] may cause
performance degradation in some languages when training a single language-
agnostic sub-network. Mixing languages in a training batch can also create
conflicts in weight updates with different languages fighting for model
capacity, known as the negative interference effect [17, 18], making it
challenging to identify an optimal language-agnostic sub-network. A recent
study [12] proposes to train language-specific sub-networks (referred to as
pathways) jointly within the original dense multilingual model instead of
training a language-agnostic sub-network. This method employs monolingual data
in a batch to fine-tune the respective pathway without interference from other
languages. As these pathways overlap, the weights are updated either in a
language-specific or a language-agnostic manner, surpassing the performance of
language-agnostic methods. However, a drawback of the pathways method is
acquiring each pathway in a separate stage that performs monolingual training
and pruning, incurring a computational cost that scales linearly with the
number of languages. These pathways, once obtained, remain fixed throughout
the training process, lacking adaptation to the multilingual data.

In this study, we introduce an adaptive masking approach for adapting
language-specific sub-networks in monolingual or multilingual pruning
situations. Our proposed method re-evaluates the pruning mask dynamically
during training, allowing the sub-network to align better with the training
data comparing to a fixed masking approach. We first assess the benefit of
applying this technique to the monolingual case, obtaining sparse monolingual
ASR models. We then prune and adapt pathways by employing our approach in
multilingual training, evaluating the performance of a jointly fine-tuned and
pruned multilingual ASR model.

Fig. 1: Flowchart of the training and pruning process with adaptive masking
enabled for monolingual data

##  2 Related Works

Multilingual Training. The concept of training sub-networks was proposed in
the context of multi-task learning [19] and has since found applications in
multilingual training [20, 21, 22]. This approach has demonstrated an efficacy
across various domains, including self-supervised learning (SSL) [20], machine
translation [21], and language modeling [22]. Our research builds upon a
recent study [12] that emphasized the effectiveness of training language-
specific sub-networks for the supervised multilingual ASR task.

Adaptive Pruning. Previous research on adaptive pruning can be broadly
categorized based on whether the pruning masks are made trainable. One
approach [23] involves fine-tuning the trainable pruning masks on downstream
tasks while keeping the original model weights fixed, demonstrating
performance improvements over traditional fine-tuning methods. Another
approach [24] focuses on re-learning the pruned weights by lifting the mask
during training, allowing adjustments to the pruning mask without learning it
directly. This technique was applied to fine-tune a multilingual speech SSL
model for monolingual ASR tasks. In contrast to the latter approach, our study
applies adaptive masking to the supervised multilingual ASR task with
structured pruning, introducing novel strategies for attaining and adapting
sub-networks during multilingual training.

##  3 Methodology

We first recap the concept of pruning (Section 3.1). We then illustrate
current pruning methods that are foundational to our proposed approach
(Section 3.2). Finally, we described our adaptive masking approach for
monolingual and multilingual pruning (Section 3.3).

###  3.1 Pruning recap

For a dense neural network $f(x;\theta_{0})$ trained with input sample $x$ and
parameters $\theta_{0}$, we denote a sub-network $f(x;m\odot\theta_{0})$ with
a binary pruning mask $m$ and the element-wise product $\odot$. The pruning
goal is to identify the sub-network $f(x;m\odot\theta)$ through additional
training, where $\theta$ can be the parameters obtained at any stage of
training. We consider a progressive pruning schedule [7], where pruning starts
from a low sparsity and incrementally steps up to the target sparsity.

###  3.2 Current pruning methods

####  3.2.1 IMP, LTH, and LAP

The iterative magnitude pruning (IMP) method [6] involves fine-tuning a dense
model for a specified number of steps denoted as $T$ while making pruning
decisions based on the magnitude of weights. Here, the magnitude of a weight
reflects its significance to the task, with larger values indicating higher
importance. For structured pruning, we use the block-wise scheme similar to
that in [25], following a block pattern of 8 $\times$ 1\. This pattern implies
that eight consecutive weights within a column are pruned simultaneously. We
evaluate magnitudes by the L2 norm of a weight block. To initiate the IMP
procedure, we initialize model parameters $\theta$ with pre-trained dense
weights $\theta_{0}$ and set the binary pruning mask $m$ to all ones
$\mathbf{1}$, where $m\in\\{0,1\\}^{|\theta|}$.

Fig. 2: Flowchart of the training and pruning process with adaptive masking
enabled for multilingual data

The IMP procedure is illustrated as follows:

Repeat

  1. 1.

Train $f(x;m\odot\theta)$ for $T$ steps, resulting in $f(x;m\odot\theta_{T})$.

  2. 2.

Prune $p\%$ of total weights from $m\odot\theta_{T}$ that has the smallest
magnitudes. Setting the pruned positions in $m$ to 0.

  3. 3.

Assign $\theta_{T}$ to $\theta$ for the next iteration

Until $m$ reaches the target sparsity

We note the property of a pruning mask depends on the training data. When
monolingual data is used in IMP, this procedure yields a language-specific
pruning mask $m_{l}$ for a language $l$. For multilingual data, it results in
a language-agnostic pruning mask, referred to as language-agnostic pruning
(LAP). Importantly, the pruning mask remains fixed at any step within the $T$
training steps, suggesting the pruning decision is irreversible.

Table 1: WER (%) results on the MLS test set, pruning a dense multilingual ASR
model. The proposed approach allows the mask to change in training and is
compared to other pruning methods for monolingual training scenario.

Stage | Model |  Mask can change? | Sparsity |  Monolingual or Multilingual training? | EN | FR | IT | NL | Avg.
---|---|---|---|---|---|---|---|---|---
Ref. | 56M Dense | / | 0% | Monolingual | 12.15 | 16.00 | 27.62 | 23.23 | 19.75
(1) | 187M Dense | / | 0% | Multilingual | 12.91 | 10.90 | 16.94 | 17.56 | 14.58
(2) | LAP | No | 70% | Multilingual | 13.82 | 11.98 | 27.71 | 19.32 | 18.21
IMP | No | 70% | Monolingual | 10.74 | 11.26 | 17.90 | 18.38 | 14.57
LTH | No | 70% | Monolingual | 10.80 | 10.38 | 18.44 | 17.48 | 14.28
(3) | ASR Pathways (IMP-70%) | No | 70% | Multilingual | 11.15 | 10.68 | 17.53 | 16.90 | 14.06
ASR Pathways (LTH-70%) | No | 70% | Multilingual | 11.39 | 10.20 | 17.58 | 15.84 | 13.75
(2) Proposed | IMP | Yes | 70% | Monolingual | 10.07 | 10.90 | 17.21 | 16.98 | 13.79
LTH | Yes | 70% | Monolingual | 10.54 | 9.91 | 17.06 | 16.63 | 13.53

The lottery ticket hypothesis (LTH) method [8] modifies the Step 3 of the IMP
procedure by assigning the pre-trained dense weights $\theta_{0}$ to $\theta$
instead of $\theta_{T}$, referred to as a re-winding step. It assumes that a
sub-network capable of achieving performance similar to the original dense
network exists within the original dense architecture. Therefore, the LTH
method leads to the identification of a sub-network embedded within the
original dense model weights.

####  3.2.2 ASR Pathways

The ASR Pathways [12] provides a method to fine-tune a multilingual ASR model
using the language-specific sub-networks (or pathways) identified through IMP,
LTH, or other pruning methods. These sub-networks are attained at the target
sparsity level and remain fixed throughout training. The mini-batch is
configured as monolingual, while the training includes a mixture of languages
across mini-batches. This setup ensures that each mini-batch activates one
pathway and updates the weights underlying the pruning mask of this pathway,
denoted as $m_{l}\odot\theta$. Since each language-specific sub-network is a
part of the original dense multilingual model and gets fine-tuned together,
the training process results in a final sparse multilingual ASR model.

###  3.3 The adaptive masking approach

####  3.3.1 Monolingual pruning

We propose an adaptive masking approach for monolingual pruning, yielding a
language-specific pruning mask adapted with the data. We illustrate this
approach as a flowchart shown in Figure 1. Within the framework of the IMP
procedure, we introduce a mask adaptation step denoted as $n$ (where $n<T$).
During the adaptation step, we re-evaluate the sub-network configuration
(adapt) by pruning from all weights in $\theta_{n}$ with a portion $p$% that
maintains the sparsity level of the current pruning mask. Next, we prune
“softly” by setting the pruned weights to zero, denoted as $(\mathbf{1}-m)\
\odot\ \theta_{n}$, and make them trainable (masked-out). Since the masked-out
weights receive updates from training, they can form new connections within
the network and reveal an optimal configuration of the sub-network as the
training evolves. For the pruning step, we simply raise the sparsity level and
prune from all weights in $\theta_{n}$ as opposed to pruning from weights in
$m\odot\theta_{T}$ in the IMP procedure.

####  3.3.2 Multilingual pruning

We propose an adaptive masking approach for multilingual pruning based on the
pathways training method described in [12], named Dynamic ASR Pathways. We use
a similar adaptation step to the monolingual pruning and illustrate it in a
flowchart shown in Figure 2. When a mini-batch in language $z$ is processed,
we train the sub-network of this language $z$ and a “residual” sub-network,
excluding other language-specific sub-networks. Given a language set $L$
representing all languages in the data, we denote this pruning mask as,

$m_{z,r}=m_{z}\cup(\mathbf{1}-\cup_{l\ in\ L,l\neq z}m_{z})$ (1)

During the adaption step, we re-evaluate the language-specific sub-network by
pruning from weights in $m_{z,r}\odot\theta_{n}$ with its current sparsity
level held. Since the adaptation step is monolingual, the newly adapted sub-
network can become more language-specific compared to before. During the
pruning step, we simultaneously prune sub-networks by pruning from weights in
$m_{z,r}\odot\theta_{T}$, iterating over each language $z$ in the language set
$L$. Because different languages would share the “residual” sub-network
depending on the data distribution, this pruning step promotes parameter
sharing among sub-networks, compensating potential reductions in the
adaptation step.

##  4 Experimental Setup

###  4.1 Dataset

We conduct our experiments using the multilingual Librispeech (MLS) [26]
dataset, which consists of multilingual speech derived from audiobooks. Our
study focuses on four languages: English (EN), French (FR), Italian (IT), and
Dutch (NL), with respective training audio length of 44.7k hrs, 1.1k hrs, 0.2k
hrs, 1.6k hrs.

###  4.2 Implementation details

We employ a streaming RNN-T model for the dense multilingual model, using 30
Emformer layers [27] with 512 input dimensions, 2048 feed-forward dimensions,
and encoder layers with convolutional blocks [28]. This model has about 180
million parameters. We utilize word pieces to recognize spoken words in all
four languages, totaling 1548 items. For consistency, we use the same output
layer size for all training setups. The learning rate schedule is tri-stage
[29] with a peak learning rate of 1e-3. For monolingual models, we conduct
training for 100K, 80K, 50K, and 80K steps for EN, FR, IT, and NL,
respectively. The multilingual pathway model undergoes training for 200K and
100K steps for IMP and LTH methods, respectively. We also conduct a bilingual
experiment for the multilingual pathway models, where the training step is
80K. We employ an uniform data sampling scheme for the multilingual training
when Dynamic ASR Pathways method is compared, otherwise an non-uniform
sampling scheme. The prune step $T$ was set to be 8% of the training step for
each setup, with an adaption step $n$ of $100$ and a prune portion $p$ of 20%
across all experiments. Pruning was applied exclusively to linear layers in
the encoder Eformer and the predictor LSTM layers, with a uniform sparsity
across all prunable layers [25]. We implement group lasso regularization as
previously mentioned [12]. We use 16 GPUs for monolingual training and 32 GPUs
for multilingual training, with a per-GPU batch size of 28.

##  5 Results

We first show baseline results from using current pruning methods (Section
5.1). We then compare the adaptive masking approach for monolingual pruning to
its relative baseline (Section 5.2). Finally, we compare the adaptive masking
approach for multilingual pruning (Dynamic ASR Pathways) to the ASR Pathways
baseline (Section 5.3).

Table 2: WER (%) results on the MLS test set, utilizing language-specific
pruning masks. The proposed approach is compared to an existing method for the
bilingual training case.

Model |  Initialization |  Mask change? | Sparsity | FR | NL | Avg.
---|---|---|---|---|---|---
ASR Pathways | LTH-70% | No | 70% | 10.73 | 16.23 | 13.48
ASR Pathways | LAP-70% | No | 70% | 11.98 | 19.32 | 15.65
Dynamic ASR Pathways | LTH-70% | Yes | 70% | 11.31 | 15.55 | 13.43
LTH-50% | Yes | 70% | 10.48 | 14.92 | 12.70
LTH-20% | Yes | 70% | 10.99 | 16.17 | 13.58
Dynamic ASR Pathways | LAP-70% | Yes | 70% | 10.98 | 16.54 | 13.76
LAP-50% | Yes | 70% | 10.82 | 16.25 | 13.54
LAP-20% | Yes | 70% | 10.88 | 16.43 | 13.65

###  5.1 Baselines

In Table 1, we present the results of existing methods for pruning a
multilingual ASR model. We breakdown these methods into three stages: 1)
training a dense multilingual ASR model, 2) pruning the dense multilingual ASR
model, and 3) training a sparse multilingual model. For reference, we include
results of dense monolingual model. Both the IMP and LTH language-specific
pruning methods achieve matching performance to the original dense
multilingual model and surpass the dense monolingual models. The ASR Pathways
method outperforms other methods using the language-specific masks obtained in
Stage (2), promoting parameter sharing among languages.

###  5.2 Adaptive masking in monolingual pruning

In the last two rows of Table 1, we present the results of using adaptive
masking for monolingual pruning. Our proposed Stage (2) modified the IMP and
the LTH language-specific pruning methods in Stage (2) and achieved a
consistent 5.3% relative WER reduction averaged across languages. Comparing
the adapted sub-networks to the fixed ones, we noticed about an 80% similarity
and a 20% difference, indicating the effective adaptation occurs within a
small part of the pruning masks. Our proposed Stage (2) also outperforms the
sparse multilingual model obtained in Stage (3), providing an efficient
alternative when storing multiple models is not a concern.

###  5.3 Adaptive masking in multilingual pruning

In Table 2, we show the results of a bilingual experiment when using adaptive
masking for multilingual pruning. We initialized the training with the LTH or
the LAP masks at the target sparsity level (70%) and achieved a consistent
improvement when only adaptation is enabled. Notably, adapting the LAP-70%
mask achieves a 12.1% relative WER reduction, indicating the adaptation step
has effectively turned the LAP mask to become more language-specific. We
noticed a similar but improved performance when using the LTH-70% masks,
suggesting these masks may be robust at a high sparsity level.

Table 3: WER (%) results on the MLS test set, utilizing language-specific
pruning masks. The proposed approach is compared to an existing method,
extending to four languages.

Model | Initialization | Sparsity | EN | FR | IT | NL | Avg.
---|---|---|---|---|---|---|---
ASR Pathways | LTH-70% | 70% | 13.56 | 10.53 | 17.10 | 16.37 | 14.39
Dynamic ASR Pathways | LTH-50% | 70% | 14.84 | 10.35 | 16.10 | 15.15 | 14.11

22footnotetext: Due to time limitation, this result is inferred at an early
checkpoint, subject to a better future improvement

We observed the best overall performance using mask initialization at a middle
sparsity level (50%) when both pruning and adaptation steps are enabled. For
the LTH-50% mask initialization, our Dynamic ASR Pathways method outperformed
the respective ASR Pathways baseline with a 5.8% relative WER reduction. From
an analysis, we find this model results in a even lower union ratio111The
union ratio indicates the ratio between surviving parameters in the union of
all masks and the total parameters of the network [12] (0.34) compared to its
baseline (0.36), indicating a better multilingual performance is achieved
using even less total effective model parameters. We believe this effect can
be attributed to the pruning step introduced in our approach that increases
parameter sharing (Section 3.3.2). For different LAP mask initialization, we
noticed consistently a significant performance gain compared to its respective
baseline. Further, it is almost matching performance to the ASR Pathways
baseline using the LTH-70% masks, showing a benefit of efficiency with the
language-specific pruning rounds eliminated.

In Table 3, we present the extended results of applying Dynamic ASR Pathways
to pruning for more languages, initializing from the LTH-50% masks. Our
proposed approach outperforms the ASR Pathways baseline with a 2% relative WER
reduction11footnotemark: 1 on average across four languages. When considering
the performance across FR, IT, and NL, it achieves a notable 5.5% relative WER
reduction. When initializing at a 50% sparsity level, we saved additional
rounds of training and pruning for achieving a target sparsity level, showing
the efficacy of applying our approach towards efficient pruning of a
multilingual ASR model.

##  6 Conclusions

In conclusion, we proposed an adaptive masking approach for both monolingual
and multilingual pruning. In the former case, our proposed method achieved a
consistent 5.3% relative WER reduction averaged across languages and
outperformed the sparse multilingual model obtained from going through an
additional stage, offering a convenient trade-off between storage and
efficiency. In the latter case, we showed the efficacy of our approach in
pruning and adapting from different pruning mask initalizations. When
initialized from language-agnostic pruning masks, our Dynamic ASR Pathways
method showed a consistent and comparable performance to the best performance
of the ASR Pathways method that uses language-specific pruning masks,
indicating a benefit of efficiency with our approach. When initialized from
language-specific pruning masks at a 50% sparsity level, our Dynamic ASR
Pathways method outperforms the ASR Pathways method, ranging from a 2% to 5.8%
relative WER reduction. For future work, we want to scale our research of
multilingual pruning for more languages and explore the option to make pruning
masks learnable.

## References

  * [1] Yuan Shangguan, Rohit Prabhavalkar, Hang Su, Jay Mahadeokar, Yangyang Shi, Jiatong Zhou, Chunyang Wu, Duc Le, Ozlem Kalinli, Christian Fuegen, and Michael L. Seltzer,  “Dissecting User-Perceived Latency of On-Device E2E Speech Recognition,”  in Interspeech 2021.
  * [2] Yanzhang He, Tara N Sainath, Rohit Prabhavalkar, Ian McGraw, Raziel Alvarez, Ding Zhao, David Rybach, Anjuli Kannan, Yonghui Wu, Ruoming Pang, et al.,  “Streaming end-to-end speech recognition for mobile devices,”  in ICASSP 2019.
  * [3] Zhifu Gao, Yiwu Yao, Shiliang Zhang, Jun Yang, Ming Lei, and Ian McLoughlin,  “Extremely Low Footprint End-to-End ASR System for Smart Device,”  in Interspeech 2021.
  * [4] Vineel Pratap, Anuroop Sriram, Paden Tomasello, Awni Hannun, Vitaliy Liptchinsky, Gabriel Synnaeve, and Ronan Collobert,  “Massively Multilingual ASR: 50 Languages, 1 Model, 1 Billion Parameters,”  in Interspeech 2020.
  * [5] Andros Tjandra, Nayan Singhal, David Zhang, Ozlem Kalinli, Abdelrahman Mohamed, Duc Le, and Michael L Seltzer,  “Massively multilingual asr on 70 languages: Tokenization, architecture, and generalization capabilities,”  in ICASSP 2023.
  * [6] Song Han, Jeff Pool, John Tran, and William Dally,  “Learning both weights and connections for efficient neural network,”  in NeuraIPS 2015.
  * [7] Michael H. Zhu and Suyog Gupta,  “To prune, or not to prune: Exploring the efficacy of pruning for model compression,”  in ICLR 2018.
  * [8] Jonathan Frankle and Michael Carbin,  “The lottery ticket hypothesis: Finding sparse, trainable neural networks,”  in ICLR 2019.
  * [9] Yuan Shangguan, Jian Li, Qiao Liang, Raziel Alvarez, and Ian McGraw,  “Optimizing speech recognition for the edge,”  arXiv preprint arXiv:1909.12408, 2019.
  * [10] Sharan Narang, Greg Diamos, Shubho Sengupta, and Erich Elsen,  “Exploring sparsity in recurrent neural networks,”  in ICLR 2017.
  * [11] Alex Renda, Jonathan Frankle, and Michael Carbin,  “Comparing rewinding and fine-tuning in neural network pruning,”  in ICLR 2020.
  * [12] Mu Yang, Andros Tjandra, Chunxi Liu, David Zhang, Duc Le, and Ozlem Kalinli,  “Learning asr pathways: A sparse multilingual asr model,”  in ICASSP 2023.
  * [13] Arindrima Datta, Bhuvana Ramabhadran, Jesse Emond, Anjuli Kannan, and Brian Roark,  “Language-agnostic multilingual modeling,”  in ICASSP 2020.
  * [14] Kelechi Ogueji, Orevaoghene Ahia, Gbemileke Onilude, Sebastian Gehrmann, Sara Hooker, and Julia Kreutzer,  “Intriguing properties of compression on multilingual models,”  in EMNLP 2022.
  * [15] Anjuli Kannan, Arindrima Datta, Tara N. Sainath, Eugene Weinstein, Bhuvana Ramabhadran, Yonghui Wu, Ankur Bapna, Zhifeng Chen, and Seungji Lee,  “Large-Scale Multilingual Speech Recognition with a Streaming End-to-End Model,”  in Interspeech 2019.
  * [16] Genta Indra Winata, Guangsen Wang, Caiming Xiong, and Steven Hoi,  “Adapt-and-Adjust: Overcoming the Long-Tail Problem of Multilingual Speech Recognition,”  in Interspeech 2021.
  * [17] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn,  “Gradient surgery for multi-task learning,”  NeurIPS 2020.
  * [18] Uri Shaham, Maha Elbayad, Vedanuj Goswami, Omer Levy, and Shruti Bhosale,  “Causes and cures for interference in multilingual translation,”  in ACL 2023.
  * [19] Tianxiang Sun, Yunfan Shao, Xiaonan Li, Pengfei Liu, Hang Yan, Xipeng Qiu, and Xuanjing Huang,  “Learning sparse sharing architectures for multiple tasks,”  AAAI 2020.
  * [20] Yizhou Lu, Mingkun Huang, Xinghua Qu, Pengfei Wei, and Zejun Ma,  “Language adaptive cross-lingual speech representation learning with sparse sharing sub-networks,”  in ICASSP 2022.
  * [21] Zehui Lin, Liwei Wu, Mingxuan Wang, and Lei Li,  “Learning language specific sub-network for multilingual machine translation,”  in Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), 2021.
  * [22] Negar Foroutan, Mohammadreza Banaei, Rémi Lebret, Antoine Bosselut, and Karl Aberer,  “Discovering language-neutral sub-networks in multilingual language models,”  in EMNLP 2022.
  * [23] Yonggan Fu, Yang Zhang, Kaizhi Qian, Zhifan Ye, Zhongzhi Yu, Cheng-I Jeff Lai, and Celine Lin,  “Losses can be blessings: Routing self-supervised speech representations towards efficient multilingual and multitask speech processing,”  NeurIPS 2022.
  * [24] Cheng-I Jeff Lai, Yang Zhang, Alexander H Liu, Shiyu Chang, Yi-Lun Liao, Yung-Sung Chuang, Kaizhi Qian, Sameer Khurana, David Cox, and Jim Glass,  “Parp: Prune, adjust and re-prune for self-supervised speech recognition,”  NeurIPS 2021.
  * [25] Haichuan Yang, Yuan Shangguan, Dilin Wang, Meng Li, Pierce Chuang, Xiaohui Zhang, Ganesh Venkatesh, Ozlem Kalinli, and Vikas Chandra,  “Omni-sparsity dnn: Fast sparsity optimization for on-device streaming e2e asr via supernet,”  in ICASSP 2022.
  * [26] Vineel Pratap, Qiantong Xu, Anuroop Sriram, Gabriel Synnaeve, and Ronan Collobert,  “Mls: A large-scale multilingual dataset for speech research,”  arXiv preprint arXiv:2012.03411, 2020.
  * [27] Yangyang Shi, Yongqiang Wang, Chunyang Wu, Ching-Feng Yeh, Julian Chan, Frank Zhang, Duc Le, and Mike Seltzer,  “Emformer: Efficient memory transformer based acoustic model for low latency streaming speech recognition,”  in ICASSP 2021.
  * [28] Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang,  “Conformer: Convolution-augmented Transformer for Speech Recognition,”  in Interspeech 2020.
  * [29] Daniel S. Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D. Cubuk, and Quoc V. Le,  “SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognition,”  in Interspeech 2019.


# A reactive algorithm for deducing nodal forwarding behavior in a multihop
ad-hoc wireless network in the presence of errors

Karol Rydzewski, Jerzy Konorski This work was funded by National Science
Centre, Poland under grant No. UMO-2016/21/B/ST6/03146.K. Rydzewski and J.
Konorski are with Faculty of Electronics, Telecommunications and Informatics,
Gdańsk University of Technology, Gdańsk, Poland (e-mail<EMAIL_ADDRESS>jekon@eti.pg.edu.pl).

###### Abstract

A novel algorithm is presented to deduce individual nodal forwarding behavior
from standard end-to-end acknowledgments. The algorithm is based on a well-
established mathematical method and is robust to network related errors and
nodal behavior changes. The proposed solution was verified in a network
simulation, during which it achieved sound results in a challenging multihop
ad-hoc network environment.

###### Keywords:

ad hoc, networks, reputation, errors

##  I Introduction

Self-organization and node autonomy in ad-hoc networks pose many research and
engineering challenges. One important issue is nodal selfishness and a strong
microeconomic incline toward uncooperative behavior — primarily, dropping some
or all offered transit packets instead of forwarding them [1]. Many concepts
aiming at incentivizing cooperative behavior have been proposed; two main
lines of research in this area are micropayment schemes [2] and reputation
systems [3]. The presented solution comes under the latter line, and uses a
novel approach to detection of nodal forwarding behavior, the core mechanism
of every reputation system. In our research, we developed two algorithms based
on the same model to solve this problem. One of them, described and validated
with the same simulated data set, cf. reference [4], uses linear programming
enhanced with heuristics to address network errors and occasional changes in
forwarding behavior. As an output it produces for each node an interval
containing, in most cases, the node’s true percentage of forwarded packets,
thereby also providing a measure of confidence in the deduced behavior. In
contrast, the algorithm detailed in this paper uses the least squares method,
which is better suited to operate in environments where changes and errors are
prevalent. We incorporated a mechanism in the algorithm that improves the
deduction quality in volatile environments and informs users of possible
deduction error.

The remainder of this article is organized as follows: Sec. II summarizes
related works and highlights the advantages of our solution; Sec. III presents
the adopted model; Sec. IV details the deduction algorithm; Sec. V discusses
the simulation environment and the results of the algorithm’s evaluation;
finally, Sec. VI concludes the paper.

##  II Related work

In recent years, many concepts of reputation systems have been proposed for
multihop wireless networks to ensure that (selfishly) misbehaving nodes are
isolated or forced into cooperation; see reference [3] for a survey. An
essential part of such systems is a behavior detection mechanism.

Many of these systems use a watchdog mechanism [5],[6],[7],[8],[9] that relies
on omnidirectional single-channel wireless transmission for sensing packets
transmitted by a neighbor node. Its fundamental assumption is that if a node A
requests a neighbor node B to forward its packets to a remote node C, then a
watchdog at node A can also check whether node B forwards the packets to node
C. However, owing to various imperfections of wireless transmission, watchdogs
are known to be unreliable. Moreover, they do not reflect the nature and
underlying incentives of a multihop wireless network service, which consists
in source-to-destination rather than node-to-node packet transfer, thus
violating the end-to-end principle [10].

The need to derive agent reputation from a service composed of multiple agents
has been pointed out in [11]. However, research efforts to date have focused
on the explicit locations of misbehaving nodes on paths, e.g., via the two-ACK
scheme [12], node auditing [13], or end-to-end flow conservation analysis
[14].

A notable example, proposing a different approach addressing the above need,
has been presented in [15] as a a concept of selfish node detection in
military wireless sensor networks with hierarchical tree structures. In this
concept, the detection and later avoidance of malicious nodes is orchestrated
by the sink node that periodically changes the network topology and assigns a
unique encryption key to every node of the network. A source node adds a
sequence number and the node’s ID to each generated packet and encrypts the
packet. Every node further along the path adds its own ID to the packet and
encrypts it again with its own key. A sink gathers statistics on network
behavior. Given the network topology and its changes, and knowing the ratio of
delivered packets to packets sent by a given source node, the sink is able to
deduce malicious and suspected nodes in the network. Obviously, the system is
constrained to work in controlled networks, and is unfit to work in self-
organizing ad-hoc networks. Additionally, it requires an encryption component
into every network node, which can result in a prohibitive cost in some low-
powered devices.

Another, similar mechanism working in multihop ad hoc networks with OLSR
routing protocol has also been proposed [16]. The algorithm collects
information on all paths used within a given network, i.e., on the transit
nodes as well as packets sent and delivered on each path. The data are then
analyzed using a heuristic algorithm to identify misbehaving nodes. The
algorithm attempts to isolate a single node that exists only on misbehaving
paths and does not exist on any path working correctly, through comparing the
paths’ intermediate node sets. If such a node is identified, it is blamed for
the unsatisfactory performance of all paths on which it is present. As the
authors acknowledge, this method has several limitations: the network must
have a sufficiently large set of disjoint paths, the number of misbehaving
nodes must be much smaller than the number of cooperative nodes, and only a
limited number of misbehaving nodes may be detected. The algorithm is
incapable of identifying any misbehaving node when a set of misbehaving paths
exists such that there is no single node present on all of these paths, since
then at least two nodes are responsible for this situation. Similarly, the
algorithm fails to reflect reality when a single node from a set of
misbehaving paths can be isolated, but it is only partially responsible for
the decreased path performance, because there are more nodes contributing to
it. In such cases, only one node, not necessarily the worst-behaving one, is
identified and takes responsibility for all the misbehavior, whereas other
misbehaving nodes are considered fully cooperative. Fine-grained numbers
representing node behavior are then translated into one of three classes of
nodal behavior via fuzzy-logic rules. The above mechanism can be employed to
detect two types of misbehavior: dropping and delaying packets. Each of these
detection schemes is based on end-to-end acknowledgment, the former on packet
delivery statistics and the latter on the number of packets not delivered
within an a priori defined timeframe. The type of misbehavior responsible for
the resulting rating cannot be specified.

Many detection mechanisms can discern only cooperative or misbehaving nodes by
measuring their behavior against a predefined desirable pattern. Most often
they rely on threshold-based criteria or fuzzy-logic rules. Others [17] create
a finer-grained view of a node, typically with real-valued reputation levels
between 0 and 1.

The mechanism proposed in reference [16] is similar to the solution described
in this work, however, our algorithm seems more universal and robust, as
demonstrated in subsequent sections. We state the major differences between
our solution and the referenced works as follows:

  * •

The solution proposed in this work is able to detect an unlimited number of
misbehaving nodes and deduce accurately behavior levels for each of them.

  * •

The deduced behavior precisely reflects actual nodal forwarding behavior and
therefore enables a finer network response.

  * •

The algorithm provides additional information on the quality of deduction,
which can be used to assess its usefulness in a given situation.

  * •

The algorithm operates in a reactive manner and is constantly optimizing its
output to mitigate the effects of nodal behavior changes and network errors.

  * •

The proposed solution can work with any routing protocol, providing a source
node with information on all intermediate nodes on the route used.

  * •

The algorithm is based on a classical optimization problem with well-known
properties and many dedicated high-performance solvers available.

  * •

The algorithm works in any topology without the need for introducing any
supporting infrastructure, e.g., encryption or authentication. Consequently,
the algorithm does not degrade the flexibility, autonomy and performance of
the network.

  * •

Our solution does not rely on the assumption that transit nodes will cooperate
in detecting behavior of their peers, thus it is compliant with the widely
recognized end-to-end principle [10].

##  III Model

In our notation, sets are written in boldface, nodes are denoted by upper-case
letters, and lower-case symbols are reserved for various numerical
characteristics. The set of network nodes is denoted by N. For simplicity, in
the presented solution it is a static set; however, the algorithm can work
without modifications on a variable set. The traffic pattern is represented by
a set K of source-destination node pairs. If there is no wireless link between
a given source-destination node pair, then a path involving transit nodes is
established by using some single-path routing protocol. For a path k $\in$ K,
let _S k_, _D k_ $\subseteq$ N denote the source and destination nodes, and
let $\textbf{X}_{k}\subseteq\textbf{N}\setminus\\{S_{k},D_{k}\\}$ denote the
(possibly empty) set of transit nodes111The sequence of nodes in Xk is
irrelevant as long as the nodes can form a valid path between _S k_ and _D
k_..

As previously indicated, the transit nodes may selfishly drop all or part of
the offered transit packets. To incentivize a satisfactory packet forwarding
service, the network must first accurately deduce nodal forwarding behavior.
To this end, it incorporates a reputation system whose task is to deduce each
node’s forwarding behavior from observable performance characteristics. Later
use of the deduced behavior levels is beyond the scope of this work. Although
this task could be fulfilled in a distributed fashion, for ease of exposition
we assign it to a single network-wide _reputation server_ (RS). (A distributed
algorithm will be investigated in future work.) Source nodes in the network,
upon completion of each communication session, send a report on the observed
end-to-end packet delivery ratio (PDR). After receiving the report from a
source node, RS runs a dedicated algorithm that calculates each node’s
forwarding behavior level. Hence, watchdogs are dispensed with, and deducing
the individual forwarding behavior of the nodes in $\textbf{X}_{k}$ from the
PDR on path _k_ becomes the main challenge.

With regard to the forwarding behavior of a node $\emph{X}\in\textbf{N}$, we
introduce two quantities. One, denoted by $g_{X}$, is its _intrinsic
forwarding trustworthiness_ (IFT) defined as the percentage of offered transit
packets that the node is inclined to forward toward the destination. This is a
ground truth-type quantity, which is accurately observable only to node _X_
itself. The other quantity, denoted by $d_{X}$, may change as new reports are
received; it is the nodal behavior level as deduced by RS from the reported
PDRs. We have $g_{X},d_{X}\in[0,1]$, where 0 signifies a lack of cooperation
(no packet forwarding), and 1 signifies fully cooperative behavior (no packet
dropping). Ideally, $d_{X}=g_{X}$, but in reality the two quantities may
differ on account of inaccurate observation of end-to-end PDRs and possible
ambiguities produced by the underlying deduction algorithm at RS. Accurately
approximating $g_{X}$ by $d_{X}$ is critical to the viability of our
reputation system.

The proposed deduction algorithm relies on the following assumptions:

  1. i

After each packet transmission (e.g., TCP) session on path $k\in$ K, the
source node $S_{k}$ calculates and truthfully reports to RS the observed end-
to-end PDR, denoted by $p_{k}$, along with the set Xk. The presence of Xk in
the report implies that the employed routing protocol reveals all transit
nodes on path _k_ to $S_{k}$ before all packets within the session have been
transmitted toward $D_{k}$. An example is Dynamic Source Routing (DSR) [18],
an on-demand source routing protocol in which $S_{k}$ initiates a path
discovery process, and one path is returned in a reply message containing a
list of all discovered transit nodes. This list is carried in packets’ DSR
headers (and is also visible to all the nodes in Xk).

  2. ii

Node _X_ forwarding behavior with respect to an offered transit packet is
defined as an IFT-based forward/drop decision, whereby a retained packet is
forwarded with probability $g_{X}$ and dropped with probability $1-g_{X}$.

  3. iii

The forward/drop decisions at the nodes in Xk are fully autonomous and
statistically independent, and also are not selective with regard to _k_. Path
selective behavior is not assumed to occur, for simplicity of analysis,
although such behavior is generally possible [16] and will be investigated in
future work. External, e.g., temporary congestion-related factors may
influence the observed PDRs, thus possibly resulting in apparent path
selective behavior; in our model, these factors are regarded as observation
imperfections and are not explicitly modeled.

In light of assumptions i–iii, the probability of successful packet delivery
on path _k_ , as observed by $S_{k}$ through the analysis of incoming end-to-
end ACKs and later reported to RS as $p_{k}$, is determined by the path
equation:

$p_{k}=\begin{cases}{\prod\limits_{X\in\textbf{X}_{k}}}g_{X},&\textbf{X}_{k}\neq\varnothing\\\
1,&\textbf{X}_{k}=\varnothing\end{cases}$ (1)

Note that $p_{k}$ is the fully determined ground-truth IFT of the nodes in Xk.
If path _k_ contains only ideally trustworthy transit nodes (or no transit
nodes at all), then $S_{k}$ can expect an end-to-end PDR equal to 1. If path
_k_ does not contain any transit nodes (X${}_{k}=\varnothing$), $p_{k}=1$, as
$S_{k}$ is clearly interested in forwarding all of its source packets. A
similar model of $p_{k}$ in a selfish network environment has been proposed in
[19]. The path model, RS communication and nodal forwarding behaviors are
illustrated in Fig. 1.

Figure 1: Path model and communication with RS.

The centralized RS model simplifies the considerations, although a distributed
reputation system can be envisaged instead; this will be examined in future
work. In addition, we stress that the proposed deduction algorithm has
reasonable routing requirements (information on transit nodes available for
the source node prior to a session end) and can work with any number of
misbehaving nodes.

Nodal behavior levels are calculated by RS whenever a PDR report is received,
on the basis of this and all previously received PDR reports. In the next
section, we first describe the algorithm for an idealized model, and next
proceed with mechanisms for mitigating PDR observation errors, IFT changes and
possibly untruthful reporting.

##  IV Algorithm

Each source node in the network collects data on the PDR ratio ($p_{k}$) and
transit nodes (Xk) for each path (_k_) that the node uses. The data tuple
$\langle p_{k},|\textbf{X}_{k}|\rangle$ is sent to the RS upon completing a
TCP session on a given path; this tuple constitutes a PDR report. The RS
builds an equation system from all received reports according to the model
(1):

$p_{k}={\prod\limits_{Y\in\textbf{X}_{k}}}g_{Y},\forall k\in\textbf{K}$ (2)

Because a multiplicative PDR model equation is not suitable for linear
regression methods, the RS uses logarithmic transformation to obtain a system
of linear equations. Let $\widetilde{p}_{k}=-\log_{b}(p_{k})$ and
$\widetilde{g}_{X}=-\log_{b}(g_{X})$, the logarithms being to any base $b>1$.
Then (2) transforms into:

$\widetilde{p}_{k}={\sum\limits_{Y\in\textbf{X}_{k}}}\widetilde{g}_{Y},\forall
k\in\textbf{K}$ (3)

The linear system (3) is an input for a behavior deduction algorithm, which is
identical to a least-squares minimization problem:

$\text{minimize: }|A\widetilde{g}-\widetilde{p}|$ (4) $\text{subject to:
}g_{Y}\in[0,1],Y\in\textbf{N}$

where _A_ is an $|\textbf{N}|\times|\textbf{K}|$ node-path incidence matrix,
and is a $|\textbf{K}|$-dimensional column vector with a generic entry
$\widetilde{p}_{k}$. Writing $A^{T}$ for the transpose of _A_ , the solution
to (4) can be routinely obtained as:

$\widetilde{g}^{*}=(A^{T}A)^{-1}A^{T}\widetilde{p}$ (5)

and subsequently transformed to the deduced behavior level
$d_{X},X\in\textbf{N}$, using $d_{X}=\exp_{b}(-\widetilde{g}_{X}^{*})$. The
result is a scalar number representing the best possible match of all $d_{X}$
for all equations in the RS-built linear system, i.e., $d_{X}$ minimizes the
total discrepancy among $p_{k}$ (PDR observed by source nodes) and
$p_{k}^{{}^{\prime}}$ (PDR calculated by substituting $d_{X}$ into all the
equations in the system). This discrepancy is called the _residual_. In the
basic least-squares method, the error of deduction of $d_{X}$ follows from
(4). This error may be of fundamental significance if $d_{X}$ is used as a
decision factor for subsequent cooperation enforcement. To give this error,
denoted $e_{X}$, a more straightforward interpretation, we propose a method to
assess it as the maximum residual for all reported paths containing node _X_ :

$e_{X}=\begin{cases}\max_{\begin{subarray}{c}k\in\textbf{K}_{X}\end{subarray}}|p_{k}-p_{k}^{{}^{\prime}}|,&|\textbf{K}_{X}|>3\\\
penalty,&|\textbf{K}_{X}|\leq 3\end{cases}$ (6)

where $p_{k}$ is given by (2),
$p_{k}^{{}^{\prime}}={\prod\limits_{Y\in\textbf{X}_{k}}}d_{Y}$, and
$\textbf{K}_{X}=\\{k\in\textbf{K}:X\in\textbf{X}_{k}\\}$. When the number of
reported paths comprising node _X_ as a transit node is small, the $e_{X}$
value is set to an a priori defined _penalty_ value. The penalty is set to 1
(highest possible error value) to avoid yielding misleading results when the
number of reports on _X_ behavior is insufficient to yield a conclusive
estimate. Without this provision, algorithm (6) would significantly
underestimate the $e_{X}$ for such nodes. The threshold value 3 was
experimentally evaluated to provide a satisfactory balance between an
acceptable risk of a false result and the minimum sample size required to
yield informative output.

The formula (6) produces a single number that can be used to calculate an
interval within which $g_{X}$ should be located:
$g_{X}\in[d_{X}-e_{X},d_{X}+e_{X}]\cap[0,1]$. Importantly, the interval has
the following properties:

  1. 1.

It is based on source nodes’ reports; in some cases, the true $g_{X}$ may be
located outside this interval. An example of such a case is a situation where
majority of KX reports experience unusually high medium-related losses. This
may happen if a relatively small portion of a network suffers from congestive
traffic, while the rest of the network operates in more favourable conditions.
The algorithm should gradually recover as new reports are received.

  2. 2.

The interval depends on errors related to all nodes coexisting with _X_ at
least once on a path in KX. It is impossible to deduce which node is
responsible for a specific value of $e_{X}$.

One path in KX almost always resulted in a large ($|g_{X}-d_{X}+e_{X}|>0.05$)
deduction error for $X$ because of interference between the PDR-reading error
and the inherent least-squares error. Two paths in KX improved the results,
however, significant errors were observed in roughly $10\%$ of the cases. With
$|\textbf{K}_{X}|=3$ we did not observe any significant errors and even small
errors ($|g_{X}-d_{X}+e_{X}|<0.05$) were infrequent. Note that because the
results of the deduction algorithm strongly depend on the network topology and
the nodes’ IFT, it is hard to judge if the adopted threshold value is a
universally optimal choice.

In typical circumstances (without nodal behavior changes and under steady
traffic conditions), the value of the observed error initially increases with
incoming PDR reports and eventually stabilizes. Unusually large network errors
(e.g., buffer overflow, transmission impairments, MAC-layer delays, end-to-end
acknowledgment loss, PDR inaccuraccies) and nodal IFT changes result in sharp
surges in $e_{X}$. The value by which $g_{X}$ changes is correlated with the
increase in $e_{X}$. The presented solution uses $e_{X}$ values to improve the
_deduction accuracy_ (defined as $g_{X}-d_{X}$) and enable prompt response to
nodal IFT changes.

Proposed algorithm operates accordingly to Algorithm 1. Upon receipt of a new
report, RS transforms it with logarithm transformation (3), and calculates
$d_{X}$ and $e_{X}$ values for each node in N, based on the whole K, including
the newly received report. Then, RS starts search for possible optimization by
looking for a KX subset, which removal results in lowering overall $e_{X}$.
Search for improvement is continued until no suitable KX is identified for
removal or further search is impossible (e.g., all paths have been removed).

begin upon reception of a PDR report: $<p_{k}$,X${}_{k}>$

$<p_{k}$,X${}_{k}>$ _report_ $\leftarrow$ log. trans.($<p_{k}$,X${}_{k}>$);
//(3)

while  _true_ do

vector _orig._ $d_{X}\leftarrow$ deduce IFT(K$\cup$ _report_); //(5)

vector _orig._ $e_{X}\leftarrow$ estimate error (N, _orig._ $d_{X}$, K $\cup$
_report_ , penalty); //(6) for each $X\in$ N

foreach  _$X\in$ report.Xk_ do

vector $d_{X}\leftarrow$ deduce IFT((K$\setminus\textbf{K}_{X}$) $\cup$
_report_);

$e_{X}\leftarrow$ sum(estimate error(N, $d_{X}$, (K$\setminus\textbf{K}_{X}$)
$\cup$ _report_ , penalty));

end foreach

$<node,e_{X}>best\leftarrow$ min($e_{X}$);

if  _$best.e_{X}\geq$ sum(_orig._ $e_{X}$)_ then

K $\leftarrow$ K $\cup$ _report_ ;

orig. $e_{X}\leftarrow$ estimate error(N, orig. $d_{X}$, K, _penalty_ =1)
return _orig._ $d_{X}$, _orig._ $e_{X}$;

else

$\textbf{K}\leftarrow\textbf{K}\setminus\textbf{K}_{best.node}$;

end if

end while

end

Algorithm 1 A reactive algorithm for deducing IFT

Notably, removing more paths from K than necessary is undesirable because it
negatively affects deduction for all nodes in the network until new reports
are received. Because of this fact, excessive path removal should be
discouraged. Assigning an appropriate penalty value 6 is essential for
achieving a good balance between the sensitivity of the deduction algorithm
for IFT changes and the prevention of unnecessary path removal. A discussion
of the influence of the penalty values on the algorithm’s deduction accuracy
will be provided later. Note that in Algorithm 1 there is a difference between
the penalty values returned by the algorithm as an end-result, to provide
information on possible deduction errors (penalty always equals 1), and the
penalty value used to decide weather to remove KX subset (penalty $\in[0,1]$).

Another measure implemented in the presented solution restricts the maximum
size of the analyzed linear system to some predefined value called _history_ ,
denoted by _h_. This reduces the resources (memory and computing power)
required for deduction, and ensures that PDR reports produced by outdated
nodal IFT are eventually removed even if the path removal mechanism based on
$e_{X}$ differences fails to correctly identify such reports. The _h_ must be
large enough to ensure minimal disruption when paths are removed through the
$e_{X}$-based mechanism. In stable environments, longer histories guarantee
superior accuracy; in contrast, in environments where nodal IFT changes are
frequent, decreasing _h_ is beneficial as it speeds up response to nodal IFT
changes and permits to quickly return to acceptable accuracy, cf. experimental
results in Sec. V.

##  V Simulations

The simulation environment was built in OMNeT++ with the Inetmanet extension
package [20]. A simulated network was configured as a multihop ad-hoc wireless
network based on the IEEE 802.11g standard. Selected simulation parameters are
provided in Table I.

TABLE I: Selected parameters of the simulator setup. Parameter | Value
---|---
antenna | omnidirectional
nodal transmission | 1 mW
power |
receiver sensitivity | -90 dBm
transmission error | Ieee80211BerTableErrorModel
model | (”per_table_80211g_Trivellatoḋat”)[20]
MAC protocol | 9 Mbps 802.11g
EDCA | enabled
maximum queue size | 50
network layer ACK | disabled
routing protocol | DSR, route request period = 1 s
transport protocols | TCP
| UDP (only for to- and from-RS messages)
TCP mode | DumbTCP [20]
TCP settings | disabled: delayed ACK, selective ACK,
| Nagle’s algorithm [21];
| maximum segment size = 1452 B,
| advertised window = 65535
simultaneously active | 1-4
TCP sessions |
nodal behavior | 0.5-1.0

Node locations, as depicted in Fig. 2 along with the available wireless links,
were invariable throughout the simulations. However, source-destination pairs
were randomly selected for each path (thus implying randomly selected transit
nodes). Moreover, initial nodal IFTs were randomly assigned at simulation
startup. Hence, the examined network topology was somewhat different in every
simulator run. Additionally, other networks, with varying numbers (up to 15)
and location of the nodes, were examined in parallel to this research and
similar results were achieved. Multiple traffic patterns were examined, in
which the average packet loss ratio due to network error (mostly buffer
overflow) fluctuated below 5%, with sporadic spikes up to 11–12%.

Figure 2: Network used in simulations (wireless links marked with solid
lines).

Nodal IFTs varied according to a stochastic model. An input to this model was
the mean number of initiated sessions between singular behavior changes in the
entire population of nodes, denoted by $\tau$. On the basis of $\tau$ and the
total number of nodes in the network, $|\textbf{N}|$, the probability of IFT
change for a single node ($c_{g}$) per initiated session was calculated as:

$c_{g}=\frac{1}{\tau|\textbf{N}|}$ (7)

Subject to the above stochastic model, changes in a node’s IFT were simulated
when the node was chosen to be a transit node on a newly created path on
condition that it was not currently serving as a transit node on another
active path. We chose such a model to simplify the control and analysis of
nodal behavior changes. Alternatively, the behavior could change during an
active session, resulting in the effective nodal behavior during that session
being some combination of the initial and the new behavior. (An extreme option
would be for a node to behave differently during any two different sessions;
we conjecture that the algorithm should be able to perform correctly under
such a model as well, however, because of the additional complexity of
configuring the algorithm properly, we defer this to future work.) The new
behavior of a node was stochastically drawn according to a uniform
distribution within the assumed domain for the simulations
($g_{X}\in[0.5,1]$). Six $\tau$ values were used: $\\{10,50,100,150,200\text{
and }\infty\\}$, with multiple simulation runs performed for each. The
presented algorithm for behavior deduction and observed error evaluation was
examined on uniformly prepared traffic generation data. The influence of the
penalty and history parameters was evaluated and compared with the standard
least-squares method not featuring these parameters (5). A total of 483
combinations of penalty and history parameters were examined, where
$penalty\in\\{0,0.05,0.1,0.15,…,0.95,1\\}$ and
$h\in\\{1,25,50,75,…,475,550\\}$.

Figure 3: Average absolute accuracy in relation to penalty and history
settings in the deduction algorithm, (a) $\tau=10$, (b) $\tau=100$; for
clarity, values above 0.08 in (a) and 0.028 in (b) were reduced to these
values.

Fig. 3 presents the average absolute value of deduction accuracy
($|g_{X}-d_{X}|$) in two simulation runs with different $\tau$ values
($\tau=10$ in Fig. 2a and $\tau=100$ in Fig. 2b in relation to variable $h$
and _penalty_ parameters (exploring their full spectrum studied in the
experiment). Steep spikes appear for low values of either: insufficient
numbers of reports (low _h_) render accurate deduction impossible and result
in high $e_{X}$ rates; similarly, low _penalty_ values do not prevent
excessive path removal, and the deduction algorithm is fed with an
insufficient number of path reports. The shape of the surface beyond these
extremely low values depends on the frequency of changes. For low $\tau$
values, the deduction accuracy achieves the lowest values for _penalty_ in the
lower part of its spectrum, e.g., _penalty_ $\in(0.1,0.4)$ for $\tau=10$. The
_h_ values have limited influence; generally, _h_ in the upper end of the
tested range yield the smallest deduction accuracy for comparable _penalty_ ;
however, in environments where IFT changes are prevalent, a short history may
yield better results. The lower the IFT change frequency (i.e., the larger
$\tau$), the more level the surface become; in such stable environments, high
values of both penalty and history yield the best results.

Figure 4: Outcome of the least-squares algorithm, (a) the simple variant, (b)
enhanced variant with path removal and limited history; solid lines: average
$|g_{X}-d_{X}|$ for all the nodes, dotted lines: maximum $|g_{X}-d_{X}|$.

Fig. 4 compares the results achieved by the deduction algorithm with and
without its error-reacting component (6) (respectively, Fig. 4b and Fig. 4a).
In both plots, two values are plotted in relation to the number of
consecutively received reports: average $|g_{X}-d_{X}|$ (solid line) and
maximum $|g_{X}-d_{X}|$ (dotted line). The outcome in Fig. 4b was achieved
with _penalty_ = 0.85 and $h=325$, which are the highest _penalty_ and $h$
values among a group of the lowest $|g_{X}-d_{X}|$ results observed in Fig.
3b. The nodal IFT change frequency was $\tau=100$. The IFT changes and
significant network errors were quickly detected, and the linear system at RS
was aptly trimmed. Acceptable average deduction accuracy was kept, and the
most erroneous $d_{X}$ values were quickly fixed. In contrast, the standard
least-squares algorithm was incapable of adapting to nodal IFT changes and
keeping the deduction accurate.

The simulation results demonstrate that report removal to minimize $e_{X}$ and
history restriction are effective means of improving behavior deduction
accuracy when changes in IFT behavior are prevalent. It was demonstrated that
by manipulating the _penalty_ and $h$ parameters, decreasing in a volatile
environment and increasing in a stable environment, the algorithm performance
can be adjusted to produce acceptable results and short response times under
various traffic conditions.

##  VI Conclusion

A novel algorithm for deducing nodal individual forwarding trustworthiness
(IFT) on the basis of end-to-end acknowledgements was presented. The algorithm
is based on a well-established mathematical method and incorporates apparatus
enhancing its deduction performance in volatile network environments, as well
as offers additional information on the deduction error. As such, it offers
satisfactory situational awareness and live insight into algorithm’s
performance.During extensive network simulations, the solution was
demonstrated to be robust to network-related errors as well as nodal IFT
changes, and to achieve significantly better results than existing algorithms.

A decentralized deduction algorithm, working with other types of routing
algorithms and better suited for mobile networks, and a scheme to incentivize
cooperative nodal behavior based on the presented solution are avenues of
near-future research.

## References

  * [1] Z. Li and H. Shen, “Analysis the cooperation strategies in mobile ad hoc networks”, Proceedings MASS 2008, Atlanta, GA, Oct. 2008. DOI: 10.1109/MAHSS.2008.4660129.
  * [2] L. Buttyan and J-P. Hubaux, “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks”, ACM J. Mobile Networks (MONET), special issue on Mobile Ad Hoc Networks, 2002. DOI: 10.1023/A:1025146013151
  * [3] K. Hoffman, D. Zage and C. Nita-Rotaru, “A survey of attack and defense techniques for reputation systems”, ACM Computing Surveys, vol. 42, issue 1, Dec. 2009. DOI: 10.1145/1592451.1592452
  * [4] J. Konorski and K. Rydzewski, “Guessing Intrinsic Forwarding Trustworthiness of MANET Nodes from End-to-End Packet Delivery”, 11th EAI International Conference, ADHOCNETS 2019, Queenstown, New Zealand, Nov. 18–21, 2019.
  * [5] S. Buchegger and J.-Y. L. Boudec, “Performance analysis of the CONFIDANT protocol”, Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, pp. 226-236, 2002.
  * [6] P. Michiardi and R. Molva, “CORE: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks,” Proc. 6th IFIP Communication and Multimedia Security Conference, Portoroz, Slovenia, pp. 107-121, 2002.
  * [7] S. Gupta and C. Kumar, “An intelligent efficient secure routing protocol for MANET”, Int. J. Future Generation Communication and Networking, vol. 6, no. 1, pp. 111-131, Feb. 2013.
  * [8] M. T. Refaei, L. A. DaSilva, M. Eltoweissy, and T. Nadjem, “Adaptation of reputation management systems to dynamic network conditions in ad hoc networks”, IEEE Transactions Computers, vol. 59, no. 5, pp. 707-719, May 2010.
  * [9] E. Chiejina, H. Xiao and B. Christianson, “A Dynamic Reputation Management System for Mobile Ad Hoc Networks”, Computers 4(2): 87-112, 2015. DOI: 10.3390/computers4020087
  * [10] J. H. Saltzer, D. P. Reed, and D. D. Clark, ”End-to-End Arguments in System Design”, ACM Transactions on Computer Systems 2.4, pp. 277-288, 1984.
  * [11] M.A. Paracha, S. Ahmad, A. Akram and M.W. Anwar, “Cooperative Reputation Index Based Selfish Node Detection and Prevention System for Mobile Ad hoc Networks”, Research Journal of Applied Sciences, Engineering and Technology 4(3):201-205, Apr. 2012.
  * [12] K. Gopalakrishnan and V.R. Uthariaraj, “Acknowledgment based Reputation Mechanism to Mitigate the Node Misbehavior in Mobile Ad Hoc Networks”, Journal of Computer Science 7 (8): 1157-1166, 2011. DOI: 10.3844/jcssp.2011.1157.1166
  * [13] Y. Zhang, L. Lazos and W.J. Kozma, “AMD: Audit-Based Misbehavior Detection in Wireless Ad Hoc Networks”, IEEE Transactions on Mobile Computing, vol. 15, no. 8, Aug. 2016. DOI: 10.1109/TMC.2012.257
  * [14] K. Graffi, P. S. Mogre, M. Hollick, and R. Steinmetz, “Detection of colluding misbehaving nodes in mobile ad hoc and wireless mesh networks”, Proceedings IEEE GLOBECOM, Washington DC, Nov. 2007. DOI: 10.1109/GLOCOM.2007.966
  * [15] S. Sivanantham, K. Kirankumar and V. Akshaya, “Detection and Avoidance of Intrusion, Packet Drop and Modification in WSN”, International Journal of Advanced Research in Computer and Communication Engineering, Vol. 2, Issue 11, Nov. 2013.
  * [16] S. Tan, X. Li and Q. Dong, “A Trust Management System for Securing Data Plane of Ad-Hoc Networks”, IEEE Transactions on Vehicular Technology, vol. 65, no. 9, Sep. 2016. DOI: 10.1109/TVT.2015.2495325
  * [17] J. Konorski and R. Orlikowski, “A reputation system for MANETs and WSNs using traffic shedding”, : 3rd International Symposium on Applied Sciences in Biomedical and Communication Technologies , Rome, Italy, Nov. 2010. DOI: 10.1109/isabel.2010.5702858
  * [18] D. Johnson, D. Maltz, and J. Broch, ”DSR: The Dynamic Source Routing Protocol for Multi-hop Wireless Ad Hoc Networks”, Boston, MA: Addison-Wesley, 2001.
  * [19] K. J. Ray Liu and B. Wang, “Repeated games and learning for packet forwarding”, Cognitive Radio Networking and Security A Game-Theoretic View, Cambridge University Press, pp. 270-296, Oct. 2010. DOI: 10.1017/CBO9780511778773
  * [20] OpenSim.Ltd, https://omnetpp.org/
  * [21] J. Nagle, “Congestion Control in IP/TCP Internetworks”, Request for Comments 896, IETF, Jan. 1984.DOI: 10.17487/RFC0896