Esercizio 29rete di sensori con slotted ALOHA (tema d'esame gennaio 2021)

---

Teoria usata: Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMAQuando più nodi condividono un mezzo serve un protocollo di accesso (MAC). Accesso deterministico: FDMA (una banda per utente) e TDMA (uno slot per utente in una trama): nessuna collisione, a ogni utente $\frac{R_b}N$ meno le perdite di sincronismo. Accesso aleatorio: ALOHA puro ($S=Ge^{-2G}$, massimo $\frac1{2e}=0{,}184$ in $G=0{,}5$), slotted ALOHA ($S=Ge^{-G}$, massimo $\frac1e=0{,}368$ in $G=1$), CSMA (si ascolta prima di trasmettere: nel non persistente $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, con $a=\frac{\tau_P}{t_P}$ piccolo si arriva a $\approx0{,}8$-$0{,}9$).Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMA →, PSK - modulazione di faseNella PSK l'informazione sta solo nella fase della portante: $s_m(t)=h(t)\cos(2\pi f_0t+\varphi_m)$ con $\varphi_m=\frac\pi M(2m-1)$. I punti stanno su una circonferenza di raggio $\sqrt{E_s}$ (tutti con la stessa energia $E_s=\frac{E_h}2$), con $d_{min}=2\sqrt{E_s}\sin\frac\pi M$. $P[E]\approx2Q\left(\sqrt{\frac{2E_s}{N_0}}\sin\frac\pi M\right)$ per $M>2$; con Gray $P_{bit}\approx\frac2{\log_2M}Q\left(\sqrt{2\Gamma}\sin\frac\pi M\right)$, $\Gamma=\frac{E_s}{N_0}$. Per $M=2$ è l'antipodale (BPSK), per $M=4$ coincide con la 4-QAM.PSK - modulazione di fase →, Confronto tra modulazioni - banda, SNR di riferimento ed efficienza spettralePer confrontare le modulazioni si usa l'SNR di riferimento $\Gamma=\frac{E_{s,rc}}{N_0,T,B_{min}}=\frac{P_{tx}}{kT_{eff}B_{min}a_{ch}}$, con $B_{min}$ la banda minima ($\frac1{2T}$ per la PAM in banda base, $\frac1T$ per QAM e PSK, $\frac M{2T}$ per le ortogonali). Ogni modulazione ha una $P_{bit}(\Gamma)$ approssimata (tabella) e un'efficienza spettrale $\nu=\frac{R_b}{B_{min}}$, limitata da Shannon: $\nu\le\log_2(1+\Gamma)$. A SNR alto conviene la QAM, a SNR molto basso le ortogonali e biortogonali (ma con più banda).Confronto tra modulazioni - banda, SNR di riferimento ed efficienza spettrale →, SNR di quantizzazione e progetto del quantizzatoreL'SNR di quantizzazione è $\Lambda_q=\frac{M_a}{M_e}$. Con errore granulare uniforme e saturazione trascurabile vale $\Lambda_q=\frac{\sigma^2}{\Delta^2/12}=3\frac{\sigma^2}{V_{sat}^2},2^{2b}$, cioè $[\Lambda_q]{dB}=6{,}02,b+4{,}77+20\log{10}\frac\sigma{V_{sat}}$: ogni bit in più dà $+6$ dB. Per progettare: $V_{sat}$ dalla probabilità di saturazione ($V_{sat}=\sigma,Q^{-1}\left(\frac{P_{sat}}2\right)$ per un gaussiano), poi $b$ dall'SNR richiesto, arrotondando per eccesso.SNR di quantizzazione e progetto del quantizzatore →, Mezzi di trasmissione - cavi, fibre e collegamenti radioIl mezzo di trasmissione fissa l'attenuazione $a_{ch}$ nel link budget. Nei cavi $H_{ch}=e^{-\gamma d}$ e l'attenuazione in dB cresce con la distanza ($a=\tilde a,d$, dB/km) e con $\sqrt f$. Le fibre ottiche hanno banda larghissima (10¹⁴-10¹⁵ Hz), attenuazione bassa in tre finestre di lunghezza d'onda e limitazione dalla dispersione. Nei collegamenti radio vale la formula di Friis, $g_{ch}=g_{tx}g_{rx}\left(\frac\lambda{4\pi d}\right)^2$, cioè $a_{ch}=32{,}4+20\log_{10}d_{km}+20\log_{10}f_{MHz}-G_{tx}-G_{rx}$ dB.Mezzi di trasmissione - cavi, fibre e collegamenti radio →.

Modello (slotted ALOHA)

Il canale ha slot lunghi quanto un pacchetto e i nodi trasmettono in modo casuale con ritrasmissione dopo un backoff: è lo slotted ALOHA (Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMAQuando più nodi condividono un mezzo serve un protocollo di accesso (MAC). Accesso deterministico: FDMA (una banda per utente) e TDMA (uno slot per utente in una trama): nessuna collisione, a ogni utente $\frac{R_b}N$ meno le perdite di sincronismo. Accesso aleatorio: ALOHA puro ($S=Ge^{-2G}$, massimo $\frac1{2e}=0{,}184$ in $G=0{,}5$), slotted ALOHA ($S=Ge^{-G}$, massimo $\frac1e=0{,}368$ in $G=1$), CSMA (si ascolta prima di trasmettere: nel non persistente $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, con $a=\frac{\tau_P}{t_P}$ piccolo si arriva a $\approx0{,}8$-$0{,}9$).Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMA →). Il pacchetto è lungo $L=1000+3\cdot8=1024$ bit, quindi lo slot dura $$t_P=\frac L{R_b}=\frac{1024}{2\cdot10^6}=512\ \mu\text{s}.$$

(1) Rate massimo per sensore

Il throughput normalizzato dello slotted ALOHA è $S=Ge^{-G}$ con massimo $S_{max}=\frac1e=0{,}368$ ($G=1$). I pacchetti ricevuti con successo al secondo, nel caso migliore, sono $\frac{S_{max}}{t_P}=\frac{0{,}3679}{512\ \mu\text{s}}=718{,}5$ pacchetti/s per tutta la rete; divisi tra $N=15$ sensori: $$\lambda_{max}=\frac{718{,}5}{15}=47{,}9\ \text{pacchetti/s per sensore}\ (\approx49\ \text{kbit/s}).$$ (Con $N=15$ il massimo esatto, $S=Nq(1-q)^{N-1}$ per $q=\frac1N$, è $0{,}380$: $49{,}6$ pacchetti/s.) Per confronto, con un accesso deterministico ideale (TDMA, senza collisioni) ogni sensore potrebbe inviare $\frac{R_b}{NL}=130{,}2$ pacchetti/s ($133$ kbit/s): è il rate che si ottiene se si interpreta la domanda come "capacità divisa equamente".

(2) Bit-rate con throughput normalizzato $S=5\%$

Il throughput normalizzato dell'intera rete è $S=0{,}05$: il $5\%$ del tempo contiene pacchetti ricevuti correttamente. Pacchetti al secondo: $\frac{0{,}05}{512\ \mu\text{s}}=97{,}66$ per tutta la rete, cioè $\frac{97{,}66}{15}=6{,}51$ pacchetti/s per sensore. Il bit-rate per sensore, contando tutti i bit del pacchetto, è $$R_s=\frac{S\,R_b}N=\frac{0{,}05\cdot2\cdot10^6}{15}=6{,}67\ \text{kbit/s}$$ (i soli bit di dati: $6{,}51$ kbit/s).

(3) Ritardo medio

A $S=0{,}05$ si ha traffico offerto $G$ tale che $Ge^{-G}=0{,}05$, cioè $G=0{,}0527$ (la soluzione piccola): quasi nessuna collisione. Probabilità di successo per tentativo $e^{-G}=0{,}9487$; numero medio di tentativi $\frac1{0{,}9487}=1{,}054$, quindi $0{,}0541$ ritrasmissioni in media. Modello: ogni tentativo occupa uno slot ($t_P$), ogni collisione costa un nuovo slot più il backoff medio ($8$ ms), e alla fine si aggiunge il ritardo di propagazione $\tau_P=\frac{15\ \text{km}}{3\cdot10^8\ \text{m/s}}=50\ \mu$s: $$E[T]=t_P+\tau_P+0{,}0541\,(t_P+8\ \text{ms})=0{,}512+0{,}050+0{,}0541\cdot8{,}512=1{,}02\ \text{ms}.$$ Il ritardo è dominato dalla trasmissione e dalla propagazione ($0{,}56$ ms); le ritrasmissioni, rare, aggiungono $0{,}46$ ms. (Se si ignorasse il traffico e si contasse un backoff per pacchetto, $8{,}6$ ms: valore molto più alto e non coerente con $S=5\%$.)

(4) Valore di $M$ per la $M$-PSK

La banda a disposizione è $B=101-100{,}5=0{,}5$ MHz $=500$ kHz. Per una modulazione passa-banda $B_{min}=\frac1T$ (Confronto tra modulazioni - banda, SNR di riferimento ed efficienza spettralePer confrontare le modulazioni si usa l'SNR di riferimento $\Gamma=\frac{E_{s,rc}}{N_0,T,B_{min}}=\frac{P_{tx}}{kT_{eff}B_{min}a_{ch}}$, con $B_{min}$ la banda minima ($\frac1{2T}$ per la PAM in banda base, $\frac1T$ per QAM e PSK, $\frac M{2T}$ per le ortogonali). Ogni modulazione ha una $P_{bit}(\Gamma)$ approssimata (tabella) e un'efficienza spettrale $\nu=\frac{R_b}{B_{min}}$, limitata da Shannon: $\nu\le\log_2(1+\Gamma)$. A SNR alto conviene la QAM, a SNR molto basso le ortogonali e biortogonali (ma con più banda).Confronto tra modulazioni - banda, SNR di riferimento ed efficienza spettrale →), quindi la frequenza di simbolo è $\frac1T=500$ ksimboli/s. Il bit-rate del canale è $R_b=2$ Mbit/s $=\frac{\log_2M}T$: $$\log_2M=\frac{R_bT}{1}=\frac{2\cdot10^6}{5\cdot10^5}=4\ \Longrightarrow\ M=2^4=16.$$

(5) SNR di quantizzazione (solo errore granulare)

$a=2x-2$ ha media $2\cdot1-2=0$ e deviazione standard $\sigma_a=2\cdot2=4$ V ($\sigma_a^2=16\ \text{V}^2$), quindi potenza statistica $16$ V². Con $b=7$, $L=128$ e $V_{sat}=12$ V: $\Delta=\frac{24}{128}=0{,}1875$ V e $$\Lambda_q=\frac{\sigma_a^2}{\Delta^2/12}=\frac{16}{0{,}1875^2/12}=5461\ \Longrightarrow\ 37{,}4\ \text{dB}.$$ (Formula: $6{,}02\cdot7+4{,}77+20\log_{10}\frac4{12}=42{,}14+4{,}77-9{,}54=37{,}4$ dB.)

(6) L'errore di saturazione si può trascurare?

$\frac{V_{sat}}{\sigma_a}=3$: $P_{sat}=2Q(3)=2{,}7\cdot10^{-3}$, piccola ma non trascurabile come potenza dell'errore: i campioni saturati hanno errori grandi. L'integrazione numerica ($M_{sat}=2\int_{12}^\infty(u-11{,}9)^2p(u)\,du$) dà $M_{sat}=7{,}1\cdot10^{-3}\ \text{V}^2$, più del doppio dell'errore granulare $\frac{\Delta^2}{12}=2{,}9\cdot10^{-3}\ \text{V}^2$. L'SNR vero è $$\Lambda_q=\frac{16}{2{,}9\cdot10^{-3}+7{,}1\cdot10^{-3}}\approx32{,}0\ \text{dB},$$ cioè $5{,}3$ dB meno del valore granulare: no, non si può trascurare (con $7$ bit e $V_{sat}=3\sigma$ domina la saturazione; per ridurla servirebbe $V_{sat}\ge4\sigma=16$ V).

(Verificato con Python: $t_P=512\ \mu$s, $\frac1e/t_P=718{,}5$ pacchetti/s, $G=0{,}052706$, $E[T]=1{,}0227$ ms, $\Lambda_{granulare}=37{,}37$ dB, $\Lambda_{totale}=32{,}03$ dB. La soluzione a mano del Drive risponde "sì, trascurabile" guardando solo $P_{sat}=2{,}7\cdot10^{-3}$.)

Errori comuni

• Dimenticare i $3$ byte di header ($L=1024$ bit, non $1000$).
• Dire che la rete può generare tutta la capacità $\frac{R_b}N$: con accesso casuale il massimo è $\frac1e$ di slot utili.
• Contare un backoff da $8$ ms per ogni pacchetto: solo i pacchetti in collisione lo pagano.
• Concludere che $P_{sat}$ piccola implica errore di saturazione trascurabile: conta la potenza dell'errore, non solo la probabilità.