Aiuto con algoritmo di ricezione saltellamento del canale pseudo-casuale

1

Prima un po 'di background del problema. Ho un trasmettitore e un ricevitore, a proposito, il trasmettitore esiste già e devo sviluppare il ricevitore.

Il trasmettitore trasmette costantemente alcuni dati e lo fa trasmettendo una volta ogni minuto. Trasmette solo una volta per canale ed è saltellante in uno schema pseudo-casuale su 50 canali diversi (ch0 ~ ch49). Quindi, trasmette in un canale diverso ogni minuto. La durata di ogni trasmissione è di circa un paio di millisecondi e anche il passaggio tra i canali del ricevitore è di un paio di millisecondi. Si può tranquillamente presumere che sia la durata della trasmissione sia il tempo di commutazione del canale siano istantanei.

Una volta terminato con tutti i 50 canali, ripete la sequenza nuovamente nello stesso ordine. Quindi l'ordine dei canali è casuale (sconosciuto) ma la sequenza è sempre la stessa.

Un meccanismo di hopping RX automatico standard non può essere implementato perché il trasmettitore non sta trasmettendo alcun preambolo e, a causa di ciò, il ricevitore non può sincronizzarsi con il trasmettitore usando un preambolo trasmesso, quindi questa non è una soluzione .

Ovviamente, il ricevitore non può ricevere dati se non è sintonizzato sul canale corretto.

Quindi l'algoritmo che ho bisogno di sviluppare deve essere in grado di identificare l'ordine dei canali che il trasmettitore sta usando per saltare in modo che il ricevitore e il trasmettitore possano essere sincronizzati.

Ho pensato a una possibile soluzione, ma non so se sia la più efficiente.

Quello che faccio è sintonizzare il ricevitore su ogni canale in una sequenza ordinata, da ch0 a ch49 e registrare il tempo in minuti ogni volta che ricevo i dati, quindi eseguo l'operazione MODULO a tutti i minuti registrati per ottenere la sequenza corretta. Ad esempio, ho il seguente esempio:

Ordered
Pattern
used
for          Recorded
channel      Time
discovery    (Minutes)

 0              0
 1             33
 2             34
 3             51
 4             78
 5            114
 6            132
 7            181
 8            197
 9            211
10            217
11            221
12            222
13            265
14            291
15            320
16            323
17            346
18            358
19            380
20            409
21            452
22            494
23            535
24            553
25            556
26            566
27            587
28            605
29            645
30            679
31            724
32            727
33            739
34            769
35            813
36            838
37            854
38            899
39            925
40            926
41            962
42           1007
43           1036
44           1040
45           1048
46           1068
47           1093
48           1142
49           1160

In questo esempio, comincio da ch0 così quando ricevo i dati su ch0 avvio la sequenza "discovery" . Nella tabella sopra si può vedere che una volta che ricevo i dati su ch0, allora salgo su ch1 e aspetto finché non ricevo dati su questo canale.

Essendo su ch1 ricevo dati 33 minuti dopo che è avvenuta la ricezione su ch0 , quindi la ricezione su ch2 è 34 minuti dopo che la ricezione è avvenuta su ch0 , la ricezione su ch3 è 51 minuti dopo la ricezione avvenuta su ch0 e così via. Infine, la ricezione su ch49 è 1160 minuti dopo la ricezione su ch0 .

Infine, quando ho i tempi per tutti i canali, ottengo l'ordine corretto ottenendo il MODULO di Recorded_Time_Minutes MOD 50 .

Dopo aver eseguito questa operazione su ogni Recorded_Time_Minutes nella tabella, ho la sequenza corretta.

Ordered
Pattern
used
for          Recorded
channel      Time
discovery    (Minutes)   Time MOD 50

 0             0               0
 1            33              33
 2            34              34
 3            51               1
 4            78              28
 5           114              14
 6           132              32
 7           181              31
 8           197              47
 9           211              11
10           217              17
11           221              21
12           222              22
13           265              15
14           291              41
15           320              20
16           323              23
17           346              46
18           358               8
19           380              30
20           409               9
21           452               2
22           494              44
23           535              35
24           553               3
25           556               6
26           566              16
27           587              37
28           605               5
29           645              45
30           679              29
31           724              24
32           727              27
33           739              39
34           769              19
35           813              13
36           838              38
37           854               4
38           899              49
39           925              25
40           926              26
41           962              12
42          1007               7
43          1036              36
44          1040              40
45          1048              48
46          1068              18
47          1093              43
48          1142              42
49          1160              10

Quindi da quell'ultimo elenco, ho ora l'ordine corretto dei canali, per esempio, prima è ch0, poi ch3, poi c21, poi ch24, ecc.

Il problema con questo metodo è che ci vogliono 1160 minuti per completare, cioè 19 ore e 20 minuti !!

In teoria, la minima quantità di tempo che impiegherebbe con questo approccio è di 50 minuti se la sequenza risulta essere in ordine da ch0 a ch49 e il peggio sarebbe 41 ore e 40 minuti se la sequenza è in ordine discendente da ch49 a ch0. Ma nessuno di questi due scenari accadrebbe mai perché, per necessità, il trasmettitore non può trasmettere in due canali adiacenti uno dopo l'altro.

NOVITÀ: osservando l'ordine di trasmissione dei canali per un dispositivo con un analizzatore di spettro, ho scoperto che due canali possono essere adiacenti, quindi l'ipotesi precedente non è più valida.

Quindi vorrei chiedere se qualcuno conosce un metodo più efficiente per ottenere la sequenza corretta di canali .

Grazie mille per l'aiuto !!

    
posta m4l490n 21.02.2017 - 22:48
fonte

2 risposte

1

Ogni minuto che controlli un canale, ottieni un'informazione. O trovi che è il canale giusto per quel minuto, o scopri che non lo è. Stai ignorando la seconda parte di questo. Per semplificare, accorciamo l'esempio in un ciclo di 5 minuti. Iniziamo con l'algoritmo fornito:

ch  min  mod
0   3    3
1   6    1
2   10   0
3   12   2
4   14   4

Quindi 15 minuti per capirlo. In realtà, è 13 perché sai qual è la risposta per gli ultimi due una volta che hai la penultima risposta.

Quindi proviamo qualcos'altro:

min ch mod result
0   0  0   N
1   1  1   Y
2   2  2   N
3   3  3   N
4   4  4   Y

Quindi siamo stati fortunati e abbiamo trovato due risposte nella prima scansione. Ma sappiamo anche altre cose. Sappiamo che ch 0 non è il primo, ch 2 non è terzo e ch 3 non è il quarto e che nessuno di questi è il secondo o il quinto. Quindi continuiamo:

min ch mod result
5   2  0   Y
6   -------------
7   0  2   N

E abbiamo finito. La logica è la seguente: la mod del minuto 5 è 0 e sappiamo già che ch 0 non è il primo e sappiamo che ch 1 è il secondo, quindi proviamo ch 2. Capita di essere il primo. Nel minuto 6, sappiamo già che Ch 1 è il secondo quindi non c'è niente da fare. Nel minuto 7, ora possiamo provare ch 0 per vedere se è terzo. Non è. A questo punto abbiamo tutte le risposte perché sappiamo che ch 3 non è 4 (8 mod 5), quindi significa che ch 0 deve essere il terzo che significa che c'è tutto sul canale 3 e una posizione rimanente. Il che ci dà risposta in circa la metà delle volte. Ovviamente il tempo necessario dipende dall'ordine. Quindi, quale sarebbe il caso peggiore? Penso che sarebbe questo:

ch mod
0  4
1  0
2  1
3  2
4  3

Ma la regola "non sequenziale" significa che l'ordine non può essere così. Se qualcuno si sente motivato a determinare la complessità del tempo per questo, sarebbe interessante di per sé. Trasformare questo in codice è lasciato al lettore, ma risponderò alle domande se l'approccio non è chiaro.

    
risposta data 27.06.2017 - 23:26
fonte
0

Il mio approccio proposto è quello di utilizzare tutte le informazioni che potresti avere sull'algoritmo che produce la sequenza per massimizzare la probabilità che il prossimo canale si aspetti. Poiché il trasmettitore non ha molte proprietà che ti aiutano, non puoi avere molti miglioramenti.

  • È pseudo-casuale e non solo casuale perché deve scorrere in una lista di numeri. Stai già utilizzando questa proprietà e hai che sta cercando la stessa lista sul lato ricevente.

  • Non può inviare inviare due canali adiacenti uno dopo l'altro. Potresti usare quella proprietà per risparmiare tempo.

Propongo di dividere l'elenco dei 50 in due elenchi: dispari e anche . Esempio: se l'ultimo canale che hai catturato è 4 non puoi avere 35 next. Pertanto, l'attesa di un numero nell'elenco dispari avrebbe minori probabilità di successo rispetto a un numero previsto nell'elenco anche . In altre parole, se prendi un numero nell'elenco dispari , è più probabile che il numero successivo nell'elenco dispari sia di nuovo più probabile. E viceversa. Ovviamente avrai puntate sbagliate molto spesso, ma un po 'meno con il tuo metodo originale.

Dato che non sono abbastanza bravo nella teoria della probabilità, non posso darti dei dati, ma mi aspetterei una riduzione del 5% nel tempo.

    
risposta data 27.02.2017 - 15:20
fonte

Leggi altre domande sui tag