1

First some background of the problem. I have a transmitter and a receiver, by the way, the transmitter already exists and I have to develop the receiver.

The transmitter is constantly transmitting some data and it does so by transmitting once every minute. It transmits just once per channel and it is hopping in a pseudo-random pattern across 50 different channels (ch0 ~ ch49). So, it is transmitting in one different channel every minute. The duration of each transmission is about a couple of milliseconds and the switching between channels at the receiver is a couple of milliseconds as well. It can be safely assumed that both, the transmission duration and the channel switching time are instantaneous.

After it has finished with all the 50 channels, it then repeats the sequence again in the exact same order. So the order of the channels is random (unknown) but the sequence is the same always.

A standard automatic RX hopping mechanism can't be implemented because the transmitter is not transmitting any preamble and because of that, the receiver can't synchronize with the transmitter by using a transmitted preamble so this is not a solution.

Obviously, the receiver can't receive any data if it is not tuned to the correct channel.

So the algorithm that I need to develop shall be capable of identifying the order of the channels that the transmitter is using to hop so that the receiver and transmitter can be in sync.

I have thought about one possible solution but I don't know if it is the most efficient.

What I do is just tune the receiver to every channel in an ordered sequence, from ch0 to ch49 and record the time in minutes every time I receive the data, then, I perform the MODULO operation to all the recorded minutes to get the correct sequence. For example, I have the following example:

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

On this example, I start from ch0 so when I receive data on ch0 I start the "discovery" sequence. In the table above it can be seen that once I receive data on ch0 I then jump to ch1 and wait until I receive data on this channel.

Being on ch1 I receive data 33 minutes after the reception occurred on ch0, then the reception on ch2 is 34 minutes after the reception occurred on ch0, then the reception on ch3 is 51 minutes after the reception occurred on ch0 and so forth. Lastly, the reception on ch49 is 1160 minutes after the reception on ch0.

Finally, when I have the times for all the channels I just get the correct order by getting the MODULO of Recorded_Time_Minutes MOD 50.

After doing this operation on every Recorded_Time_Minutes in the table I have the correct sequence.

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

So from that last list, I have now the correct order of the channels, for instance, first is ch0, then ch3, then c21, then ch24, etc.

The problem with this method is that it takes 1160 minutes to complete, that is 19 hours and 20 minutes!!

In theory, the least amount fo time that it would take with this approach is 50 minutes if the sequence happens to be in order from ch0 to ch49 and the worst would be 41 hours and 40 minutes if the sequence is in descending order from ch49 to ch0. But neither of those two scenarios would happen ever because, by requirement, the transmitter can't transmit in two adjacent channels one after the other.

NEW: By looking at the channels transmission order for one device with a spectrum analyzer I found out that two channels can be adjacent so the previous assumption is no longer valid.

So I would like to ask if somebody knows a more efficient method to get the correct sequence of channels.

Thank you very much for helping!!

  • how long (in time) transmitter is sending data every minute? how long does it take for receiver to switch to new channel and check if there is incoming transmittion? – rsm Feb 21 '17 at 22:03
  • @rsm both are instantaneous, this is, it's just some milliseconds for both cases, it can be even on the order of microseconds. – m4l490n Feb 21 '17 at 22:44
  • 2
    I think you'll need multiple coordinated receivers. Even with 49 receivers, it will still take 49 min. – Erik Eidt Feb 21 '17 at 22:58
  • @ErikEidt I can't do that, because of cost and space constraints I can only have 1 receiver. I know that I can't go below 50 minutes but that is ok. what I'm trying to achieve here is to figure out the sequence as fast as possible being 50 minutes the fastest. I just don't want it to be 19 hours or more. – m4l490n Feb 22 '17 at 15:09
  • 1
    You said "the transmitter can't transmit in two adjacent channels one after the other." But it looks like ch1 and ch2 have been transmitted one after the other. Am I wrong? – RawBean Feb 24 '17 at 10:29
1

Every minute that you check a channel, you get a piece of information. Either you find that it's the right channel for that minute, or you find out that it isn't. You are ignoring the second part of that. To simplify, let's shorten the example to a 5 minute cycle. We start with the algorithm given:

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

So 15 minutes to figure this out. Actually, it's 13 because you know what the answer is for the last two once you have the second to last answer.

So now let's try something else:

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

So we got lucky and found two answers in the first sweep. But we also know some other things. We know that ch 0 is not first, ch 2 is not third and ch 3 is not 4th and that none of these are second or fifth. So we continue:

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

And we are done. The logic is as follows: the mod of minute 5 is 0 and we already know that ch 0 is not first and we know that ch 1 is second so we try ch 2. It happens to be the first one. In minute 6, we already know that ch 1 is second so there's nothing to do. In minute 7, we can now try ch 0 to see if it is third. It's not. At this point we have all the answers because we know that ch 3 is not 4th (8 mod 5) so that means that ch 0 must be third which means every there is on channel 3 and one position remaining. Which gives us answer in about half the time. Obviously the time it takes depends on the order. So what would the worst case be? I think it would be this:

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

But the 'non-sequential' rule means the order cannot be like this. If someone feels motivated to determine time complexity for this, that would be interesting in itself. Turning this into code is left to the reader but I will answer questions if the approach is not clear.

  • It's not a trick question or an interview question, it's a real world project. And to answer your question about who would design something like this, the receiver used with these transmitter has a very wide bandwidth so it can listen to all the 50 channels at the same time so it does not have to hop, it was originally designed that way. But that solution is very expensive. So I'm trying to implement something much cheaper. I can use only small rf chips that can listen to one channel at the same time and that's why I'm posting this question – m4l490n Jun 27 '17 at 21:46
  • @m4l490n What is the point of the channel hopping? – JimmyJames Jun 28 '17 at 12:59
  • The point of channel hopping is that two or more transmitters don't interfere with each other and don't loose communication if there are another 915MHz devices nearby, like Z-Wave. Since there is no bidirectional comunnications with the transmitters there is no way to form an appropriate network, therefore all hopping at the same time in different channels each allows to receive from all of them – m4l490n Jun 28 '17 at 13:26
  • @m4l490n But if there is no collision prevention, this can only work most of the time. It doesn't seem like a robust solution. Why use a 'random' pattern? Wouldn't a DIP switch be a lot easier? It just seems like an unnecessarily complicated approach that doesn't really solve the problem well. – JimmyJames Jun 28 '17 at 13:46
  • I know, it sucks. But that's the way it is and we can't do absolutely anything to change the transmitter behavior. I mean the transmitters work fine for their original intention, but now that we want to do something else besides the only scenario that was thought for the transmitters we have to face this situation. – m4l490n Jun 28 '17 at 14:51
0

My proposed approach is to use all the information you could have about the algorithm that produce the sequence in order to maximize the probability of the next channel to expect. As the transmitter doesn't have a lot of properties helping you, you can't have a lot of improvements.

  • It's pseudo-random and not just random because it has to loop in a list of numbers. You are already using that property, and you have you are browsing the same list on the receiver side.

  • It can't send send two adjacents channels one after the other. You could use that property to save time.

I propose that you split the list of 50 into two lists: odd and even. Example: If the latest channel you catch is 4 you can't have 3nor 5 next. Therefore expecting a number in the odd list would have less chances to succeed than expecting a number in the even list. In other words, if you catch a number in the odd list, then it's more likely to have next number in the odd list again. And vice-versa. Of course you will have wrong bet very often, but a bit less than with your original method.

Since I'm not good enough in probablity theory I can't give you figures, but I would expect something like a 5% reduction in time.

  • Interesting, I will explore this approach because you are right. Maybe I can come up with something that uses this scenario. It seems indeed that it will reduce the time. – m4l490n Feb 27 '17 at 15:39
  • I am interested in knowing the final result. Please keep me informed. – RawBean Feb 27 '17 at 16:21
  • This method would not work because I found out that two channels CAN indeed be adjacent. I verified this with a spectrum analyzer. I used the spectrum analyzer to find out the sequence of one transmitter and use the results to fine-tune the algorithm, there is when I found out this. – m4l490n Jun 28 '17 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.