Algoritmo Luise-Reggiannini

L’algoritmo si pone la sfida di effettuare la stima ML della frequenza ∆f del segnale campionato:

𝑟𝑘= 𝑒𝑗(2𝜋∆𝑓𝑘𝑇𝑠+Ɵ)+ 𝜈𝑘, 1 ≤ 𝑘 ≤ 𝑁 (16) dove Ts ≤ 1/(2∆f) è l’intervallo di campionamento, Ɵ è la fase incognita con densità di probabilità uniforme in [0,2π] e νk = νk,c + jνk,s. νk,c e νk,s sono sequenze indipendenti gaussiane a media nulla con autocorrelazione Rν(k) = σ2_δk,0.

Questo problema risulta equivalente a trovare il massimo della funzione di verosimiglianza seguente [20][21]

35 dove ∆˜f è un valore provvisorio di ∆f. Non essendo possibile trovare una soluzione in forma chiusa per massimizzare l’equazione sopra, per determinare in modo esatto il valore di ∆˜f ML occorrerebbero calcoli molto complessi con tempi molto lunghi.

L’algoritmo proposto prevede dunque di calcolare la derivata di (17) rispetto ∆ ˜f ed eguagliarla a zero, ottenendo

𝐼𝑚 {∑𝑁−1𝑘(𝑁 − 𝑘)𝑅(𝑘)𝑒−𝑗2𝜋∆f 𝑘𝑇˜ 𝑠

𝑘=1 } = 0 (18)

dove R(k)è l’autocorrelazione stimata di rk,

𝑅(𝑘) ≜ 1

𝑁−𝑘∑ 𝑟𝑖𝑟𝑖−𝑘 ∗ 𝑁

𝑖=𝑘+1 , 0 ≤ 𝑘 ≤ 𝑁 − 1 (19)

Notiamo che i termini tra parentesi nell’equazione (18) possono essere visti come risultato di una trasformata discreta di Fourier di R(k) pesata dalla funzione a finestra parabolica w(k) = k(N – k), con k = 1,2,…,N-1. Tale assunzione deriva dal fatto che vicino a k = 0, la R(k) fornisce ben poca informazione sull’offset di frequenza dato che deriva da campioni del segnale molto ravvicinati. Anche per k vicino a N si otterrebbe un pessimo risultato, visto che i termini che andrebbero a concorrere tale stima sarebbero in pochi.

Il presente algoritmo propone quindi di sostituire la funzione w(k) con una sequenza di 1, con k = 1,2,…,M, M ≤ N-1, ottenendo

𝐼𝑚 {∑𝑀 𝑅(𝑘)𝑒−𝑗2𝜋∆f 𝑘𝑇˜ 𝑠

𝑘=1 } = 0 (20)

Accettando un alto CNR (Carrier-to-Noise Ratio) ed una bassa deviazione di frequenza (M∆f T≪1) è possibile approssimare l’esponenziale dell’equazione precedente con la corrispondente serie di Taylor:

∆˜f = 1 2𝜋𝑇_𝑠

∑𝑀_𝑘=1𝐼𝑚{𝑅(𝑘)}

36 Assumendo adesso che 𝑅(𝑘) = exp(𝑗2𝜋∆𝑓𝑘𝑇𝑠) + ˜ν _𝑘 ≅ 1 + 𝑗2𝜋𝑘∆𝑓𝑇𝑠+ ˜ν _𝑘 , dove |˜ν _𝑘| ≪ 1, si avrà

∑𝑀_𝑘=1𝐼𝑚{𝑅(𝑘)}≅ 𝑀𝑎𝑟𝑔{∑𝑀_𝑘=1𝑅(𝑘)} (22)

∑𝑀_𝑘=1𝑘𝑅𝑒{𝑅(𝑘)} ≅𝑀(𝑀+1)

2 (23)

dove arg(z) denota l’argomento del numero complesso z nell’intervallo [-π,π). Basandosi su queste approssimazioni l’algoritmo Luise-Reggiannini può essere scritto come

∆˜f ≅ 1

𝜋𝑇_𝑠(𝑀+1)𝑎𝑟𝑔{∑ 𝑅(𝑘) 𝑀

𝑘=1 } (24)

Le stime effettuate con questo algoritmo sono valide fintanto che l’argomento della sommatoria dell’equazione (24) non supera ±π. Questo limita il campo di aggancio dell’algoritmo all’intervallo di non ambiguità:

|∆˜f |< [(𝑀 + 1)𝑇_𝑠]−1 (25)

4.1.2 Algoritmo Mengali-Morelli

Prendiamo in considerazione una modulazione M-PSK in AWGN con densità spettrale di potenza di N0/2. Supponendo di avere al ricevitore un offset di frequenza pari a fd Hz ed effettuando un filtraggio ed un successivo campionamento agli istanti corretti si ottiene:

𝑧(𝑘) = 𝑒𝑗(2𝜋𝑓𝑑𝑘𝑇+Ɵ)_{+ 𝑛(𝑘)𝑐}

𝑘∗ (26)

L’algoritmo sfrutta le correlazioni tra i campioni,

𝑅(𝑚) = 1

𝑁−𝑚∑ 𝑧(𝑘)𝑧

∗_{(𝑘 − 𝑚), 1 ≤ 𝑚 ≤ 𝑀} 𝑁−1

37 dove N è il numero di campioni del segnale e M è un parametro non superiore a N/2. Riscrivendo l’equazione (26) nella forma 𝑧(𝑘) = 𝑒𝑗(2𝜋𝑓_𝑑𝑘𝑇+Ɵ)_{[1 + ˜n (𝑘)], con ˜n (𝑘) ≜} 𝑛(𝑘)𝑐_𝑘∗𝑒−𝑗(2𝜋𝑓𝑑𝑘𝑇+Ɵ)_{, e sostituendola nell’equazione (27) si ricava}

𝑅(𝑚) = 𝑒𝑗2𝜋𝑚𝑓𝑑𝑇[1 + 𝛾(𝑚)] ₍₂₈₎ dove 𝛾(𝑚) ≜ 1 𝑁−𝑚∑ [ ˜n (𝑘) + ˜n ∗ (𝑘 − 𝑚) + ˜n (𝑘) ˜n ∗(𝑘 − 𝑚)] 𝑁−1 𝑘=𝑚 (29)

Considerando γ(k) ≜ γr(k) + jγi(k) e rappresentando il valore dell’argomento principale di R(m) si trova:

𝑎𝑟𝑔{𝑅(𝑚)} ≈ [2𝜋𝑓_𝑑𝑇 + 𝛾_𝑖(𝑚)]_2𝜋, 1 ≤ 𝑚 ≤ 𝑀 (30)

dove [x]2π è il valore di x riportato nell’intervallo [-π,π). Da quest’ultima equazione si vede chiaramente la relazione tra fd e arg{R(m)} anche se, nella forma in cui si trova, non è ancora facilmente utilizzabile. L’algoritmo prevede allora di mettere in relazione fd con gli incrementi di fase 𝜙(𝑚) ≜ [arg{𝑅(𝑚)} − arg{𝑅(𝑚 − 1)}]_2𝜋 anziché con arg{R(m)}. In questo modo si ottiene

𝜙(𝑚) ≈ 2𝜋𝑓𝑑𝑇 + 𝛾𝑖(𝑚) − 𝛾𝑖(𝑚 − 1), 1 ≤ 𝑚 ≤ 𝑀 (31)

questo vale fintanto che |2πfdT| < π. Il problema diviene quindi quello di stimare una costante da delle misurazioni rumorose. La stima ML di fd viene indicata come

˜f _𝑑 = 1

2𝜋𝑇∑ 𝑤(𝑚)[arg{𝑅(𝑚)} − arg{𝑅(𝑚 − 1)}]2𝜋 𝑀

𝑚=1 (32)

38 𝑤(𝑚) ≜3[(𝑁−𝑚)(𝑁−𝑚+1)−𝑀(𝑁−𝑀)]

𝑀(4𝑀2_{−6𝑀𝑁+3𝑁}2₋₁₎ (33)

L’algoritmo possiede un campo di aggancio di circa ±20% della frequenza di segnalazione con una accuratezza vicina al limite di Cramer-Rao (CRB).

4.1.3 Confronto algoritmi

Le prestazioni dei due algoritmi sono state approfonditamente valutate utilizzando il software Matlab.

Come prima cosa sono state simulate delle sequenze di simboli QPSK utilizzando una frequenza di segnalazione di 1 MHz, rumore AWGN e SNR di 10dB. Gli offset utilizzati nelle sequenze spaziano da -30 KHz a + 30Khz e per entrambi gli algoritmi si è utilizzato un totale di N = 96 campioni ed un intervallo di stima di M = 47. Inoltre si ipotizza un perfetto recupero del sincronismo temporale.

Per valutare le prestazioni dei due algoritmi sono stati messi a confronto la media delle stime di frequenza ed il valore quadratico medio dell’errore di stima della frequenza.

39 Figura 31: Media Offset di Frequenza e RMS Errore di Stima con Mengali-Morelli

Nelle due figure in alto sono rappresentati i risultati ottenuti con l’algoritmo Luise– Reggiannini. Possiamo notare che le curve risultano lineari intorno all’origine, evidenziando che lo stimatore risulta non polarizzato. Quando però ∆f si avvicina alle frequenze di ambiguità ±[(𝑀 + 1)𝑇]−1, lo stimatore mostra una polarizzazione crescente e, per questo motivo, l’errore quadratico medio aumenta considerevolmente (fig. 30).

Le due figure in basso mostrano come invece le prestazioni dell’algoritmo Mengali–Morelli, avendo un campo di aggancio molto maggiore, non risentano di tale effetto e possano correttamente stimare offset di frequenza di gran lunga maggiori (±20% della frequenza di segnalazione).

Come è logico pensare, l’accuratezza della stima diminuisce al diminuire di M ma, allo stesso tempo, anche il carico computazionale dell’algoritmo diminuisce.

40 In fig. 32 viene rappresentata la varianza ottenuta con i due algoritmi con N = 128, ∆f = 0 e M = 64. La differenza si aggira sull’ordine di e-10, quindi piuttosto trascurabile.

Figura 33: Varianza Mengali-Morelli al variare di M

Infine in fig. 33 si riportano i risultati ottenuti con l’algoritmo Mengali-Morelli al variare del parametro M.

41

5. Risultati Simulazione

Le prove sono state effettuate utilizzando un dump del segnale 802.11b ricevuto da un access point sul canale 5 (2,432 MHz) e verificandone la corretta rivelazione dei beacons con i due algoritmi al variare dell’offset di frequenza. Per impostare l’offset di frequenza presente nel segnale catturato è stato ulteriormente modificato lo schema del ricevitore inserendo un blocco di Phase/Frequency Offset.

Figura 34: Schema ricevitore utilizzato per le simulazioni

È stata utilizzato un guadagno massimo di potenza dell’AGC di 60 dB con step size uguale a 6. Tali valori sono stati scelti in base alle simulazioni: osservando la finestra di controllo dell’AGC è possibile valutarne il comportamento. Se ad esempio si raggiunge il guadagno massimo anche in presenza del segnale in ingresso possiamo allora aumentare tale valore. Se invece l’AGC non risponde abbastanza velocemente ai cambiamenti di ampiezza del segnale di ingresso sarà necessario incrementare la dimensione dello step size.

Osservando la finestra dedicata alla sincronizzazione possiamo valutare se il segnale in ingresso conduce a picchi di bassa intensità che potrebbero non essere sufficienti ad attivare il ricevitore. In tal caso possiamo agire abbassando la soglia di sincronizzazione.

42 Nelle prove effettuate è stato possibile verificare che il ricevitore che implementa l’algoritmo originario Luise-Reggiannini è stato capace di rivelare correttamente i beacons nei segnali con un offset di frequenza nell’intervallo ±50 kHz.

Figura 35: Risultati Ricezione Beacons con offset massimo di -50kHz per Ricevitore Originario

Con lo stesso segnale ma utilizzando il ricevitore Mengali-Morelli è stato possibile ricevere i beacons con un offset di frequenza nell’intervallo ±125 kHz, quindi con offset di due volte e mezzo superiori rispetto a quanto sperimentato con il precedente algoritmo.

43 Una volta correttamente ricevuto il segnale è stato possibile accedere alla sezione Information Elements e leggere il campo vendor presente.

Figura 37: Dettaglio Informatio Elements su Beacon Ricevuto

Convertendo il campo OUI in esadecimale e cercandolo in una OUI Look Up Table [22] è possibile risalire alle informazioni riguardanti il produttore del dispositivo di rete. Nello specifico, i primi due OUI che vediamo in fig. 37 corrispondono a Microsoft. Il primo riporta difatti le informazioni riguardanti la modalità WPA mentre il secondo le informazioni del WME/WMM.

Il terzo campo vendor riporta invece un OUI che in esadecimale corrisponde al produttore del chipset Broadcom montato sull’access point.

44 Figura 38: Dettaglio MAC Header su Beacon Ricevuto

Utilizzando adesso i primi tre byte del source address, ovvero dell’access point nel nostro caso, per un confronto nella medesima tabella utilizzata in precedenza, si ottengono ulteriori informazioni sul produttore. Nel caso specifico abbiamo potuto identificare dai beacons un access point Netgear con chipset Broadcom.

Per motivi di tempo e di risorse non è stato possibile effettuare ulteriori prove su dati catturati da un APR.

45

6. Conclusioni

I dispositivi APR sono ormai una realtà consolidata e hanno avuto una diffusione sempre maggiore grazie alla loro versatilità nei campi più disparati. Di pari passo è quindi aumentata anche la necessità di poter disporre dei mezzi adeguati per poter controllare, rilevare e all’occorrenza inibire il loro utilizzo.

In questo lavoro di tesi è stato presentato un ricevitore IEEE 802.11b per il rilevamento e la decodifica dei beacons sviluppato da The Mathworks in cui è stato migliorato il sistema di sincronizzazione della frequenza. Questo ha permesso di rendere il dispositivo più efficiente e maggiormente adatto alla rilevazione dei beacons trasmessi da droni commerciali.

Da un’accurata analisi di questi particolari segnali è possibile identificare la sorgente e discriminare un APR da un altro comune access point.

Il front end del ricevitore è stato modificato per implementare l’algoritmo Mengali-Morelli che permette di rilevare correttamente offset di frequenza molto superiori rispetto al sistema originario. La scelta di utilizzare questo algoritmo è stata accuratamente valutata dopo numerose analisi delle prestazioni e successivo confronto con i risultati ottenuti dall’algoritmo sostituito.

Le prestazioni del ricevitore sono state testate applicando in ingresso il dump di un segnale 802.11b ricevuto da un access point sul canale 5 (2,432 MHz) e verificandone la corretta rilevazione dei beacons con i due algoritmi al variare dell’offset di frequenza.

Il sistema ottimizzato è stato capace di operare correttamente con offset di ±125 kHz contro i ±50 kHz rilevati con il ricevitore di base.

Una volta correttamente ricevuti i beacons è stato possibile identificare il produttore dell’access point ed il tipo di chipset montato.

Per motivi di tempo e di risorse non è stato possibile effettuare ulteriori simulazioni su dump di segnali reali ottenuti da APR.

Ulteriori miglioramenti del sistema potrebbero essere ottenuti utilizzando una scheda di acquisizione radio: in questo modo, tramite un’opportuna modifica nello schema del ricevitore, sarebbe possibile effettuare una rilevazione dei beacons in tempo reale.

46

7. Bibliografia

[1] IEEE Standard Definitions and Concepts for Dynamic Spectrum Access: Terminology Relating to Emerging Wireless Networks, System Functionality, and Spectrum Management, IEEE Std. 1900.1-2008, Sep. 2008.

[2] J. G. Proakis, Digital Communications, 4th ed. McGraw-Hill, 2001. [3] H. Tang, “Some physical layer issues of wide-band cognitive radio

systems” in Proc. IEEE Int. Symposium on New Frontiers in Dynamic Spectrum Access Networks, Baltimore, Maryland, USA, Nov. 2005, pp.

151–159.

[4] A. Sahai, R. Tandra, S. M. Mishra, and N. Hoven, “Fundamental design

tradeoffs in cognitive radio systems” in Proc. of Int. Workshop on Technology and Policy for Accessing Spectrum, Aug. 2006.

[5] S. t. B. S. M. Mishra, R. Mahadevappa, and R. W. Brodersen, “Cognitive

technology for ultra-wideband/WiMax coexistence” in Proc.

IEEE Int. Symposium on New Frontiers in Dynamic Spectrum Access Networks, Dublin, Ireland, Apr. 2007, pp. 179–186.

[6] A. Leon-Garcia, “Probability and Random Processes for Electrical

Engineering”. Addison Wesley, second ed., 1994.

[7] IEEE Std 802.11-2007: IEEE Standard for Information technology -

Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific requirements, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE, New York,

NY, USA, 1999-2007.

[8] Aeromobili a Pilotaggio Remoto, InfoDrones.it

47 [10] UAS Yearbook , UAS: The Global Perspective - 9th Edition - June 2011 -

Blyenburgh & Co - www.uvs-info.com - Page: 151/216, 2011-2012.

[11] Edwin Vattaparambu, ˙Ismail Guvenc,, Ali ˙I. Yurekli, Kemal Akkaya, and Selc,uk Ulua˘gac, “Drones for Smart Cities: Issues in Cybersecurity, Privacy, and Public

Safety”, Department of Electrical and Computer Engineering, Florida International

University, Miami, FL, USA

[12] S. Liberatore, “How do you catch a drone? with an even bigger drone and a giant

net” Dec. 2015. http://www.dailymail.co.uk/sciencetech/article-3356746

[13] D. Kitchen, “Drones hacking drones”, HAK5, Dec. 2013,

https://hak5.org/episodes/hak5-1518

[14] T. Witherow, “Police set to use eagles to foil terrorist drone attacks”, Feb. 2016, http://www.dailymail.co.uk/news/article-3436572

[15] M. Burns, “The skywall 100 bazooka captures drones with a giant net”, Mar. 2016, http://techcrunch.com/2016/03/04/the-skywall-100-bazooka-captures-drones-with- a-giant-net/

[16] The MathWorks, Inc, “IEEE 802.11 WLAN - Beacon Frame Receiver with Captured

Data”, 2012-2016, https://it.mathworks.com/help/comm/examples/ieee-802-11- wlan-beacon-frame-receiver-with-captured-data.html

[17] A.J. Viterbi and A.M. Viterbi, "Nonlinear estimation of PSK-modulated carrier

phase with application to burst digital transmission", IEEE Trans. Information Theory, pp. 543-551, July 1983.

[18] M. Luise and R. Reggiannini, "Carrier frequency recovery in all-digital modems for

burst-mode transmissions," IEEE Trans. Communications, pp. 1169-1178, Feb.-

March-Apr. 1995.

[19] Umberto Mengali and M. Morelli, “Data-Aided Frequency Estimation for Burst Digital Transmission”, IEEE Trans. Communications, vol. 45, no. 1, Jan. 1997.

48 [20] D. C. Rife and R. R. Boorstyn, “Single Tone Parameter Estimation from Discrete-

Time Observations”, IEEE Trans. Inform. Theory, vol. IT-20, pp. 591-598, Sept.

1974.

[21] S. A. Kay, “Modern Spectral Estimation”, Englewood Cliffs: Prentice-Hall Signal Processing Series, Oppenheim ed., 1988.

49

8. Ringraziamenti

Scrivere questa tesi è stato un lavoro lungo e non privo di difficoltà ma allo stesso tempo molto gratificante. Vorrei perciò ringraziare il Prof. Ruggero Reggiannini che mi ha sempre seguito e consigliato durante le difficoltà incontrate, così come il Prof. Michele Morelli ed il dott. ing. Marco Moretti che si sono sempre mostrati disponibili e ben disposti nei miei confronti.

Un sincero ringraziamento anche a tutte le persone che mi hanno accolto presso la struttura Intecs Spa di Montacchiello. In particolare ringrazio il mio relatore ing. Simone Gianfranceschi per l’opportunità che mi è stata data e l’ing. Luca Cucchi che, nonostante i suoi mille impegni, non ha mai mancato di trovare il tempo per ascoltarmi e seguire i miei progressi.

Come è riportato nelle prime pagine, questa tesi la dedico alla mia famiglia. Il mio papà, che nonostante le difficoltà che la vita può imporre sul nostro cammino non si ferma mai e mi è come sempre di esempio. Mia mamma che credendo sempre in me mi ha dato la forza di continuare nei miei studi. Mio fratello, Monica ed il nuovo arrivato, il piccolo Jacopo, che mi hanno sempre supportato in questi anni di studio “matto e disperatissimo”.

Infine ringrazio la mia compagna Valentina e Leo, le mie rocce, i miei punti saldi. Le mie vittorie ed i miei progressi sono anche dovuti a tutta la forza che riuscite a darmi.