WARP Project Forums - Wireless Open-Access Research Platform

You are not logged in.

#1 2016-Sep-04 20:39:46

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Algorithm involving random numbers and time synchronisation

Hi,

I want to implement an algorithm on the WARP board (based on 802.11 Reference Design) that uses two things that I think could be an issue: random numbers and connection to Network Time Protocol.

I tried to do random numbers (PRNG) putting the current time as the seed, but it always give me the same random number. Is it possible to do random number on the WARP board?

Also, I need to synchronise the time on the WARP boards through connection to Network Time Protocol. Is this feature implemented in the current 802.11 design? If not, do you think it will take a long time to implement on my own?

Regards,
loho2027

Offline

 

#2 2016-Sep-05 11:16:48

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

I tried to do random numbers (PRNG) putting the current time as the seed, but it always give me the same random number. Is it possible to do random number on the WARP board?

You can call rand() in the C code to access the stdlib PRNG. This isn't a great PRNG but is good enough for MAC purposes. This is how we generate a uniform random value when choosing backoff counts in the DCF.

Also, I need to synchronise the time on the WARP boards through connection to Network Time Protocol. Is this feature implemented in the current 802.11 design? If not, do you think it will take a long time to implement on my own?

The 802.11 ref design does not implement an NTP client. I'm not familiar with the details of NTP, but I think adding an NTP client to the embedded C code in the 802.11 design would be a big project. Can you describe the experiment requirement that you're planning to address with NTP? It's possible you can achieve the same result without the complexity of building a full NTP client.


Keep in mind the reference code does not implement any "real" time tracking. The design implements "System Time" (microseconds since boot) and "MAC Time" (microsecond timer synchronized via beacons).

The wlan_exp framework supports setting the MAC Time via Python.

It also supports sending a command that creates a TIME_INFO log entry at the node. The TIME_INFO entry records the node's MAC Time, System Time and a real time value supplied from Python. This TIME_INFO entry allows you to synchronize log entries with real time when analyzing the log data by using the TIME_INFO entries as "markers" which periodically record the relationship between the various timebases.

Offline

 

#3 2016-Sep-06 22:07:10

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

To describe my project which could require NTP, I am trying to implement the algorithm in the paper called "Decentralised Constraint Satisfaction" (http://arxiv.org/pdf/1103.3240v4.pdf).

Below is the relevant excerpt describing the need for synchronisation.

"From here on we will assume that the update Step 5 is performed in a synchronized fashion across variables. Without synchronization, the fundamental character of the algorithm doesn’t change, but the analysis becomes more involved. Synchronization solely requires that algorithm instances each have access to a shared sense of time and that this can be achieved without information-sharing or other communication between variables, i.e. between algorithm instances. A suitable clock is, for example, available to any Internet connected device via the Network Time Protocol (NTP)."

I'll probably have to start implementing the algorithm before I can determine exactly what I need, but I think in this case at least some sort of time synchronisation is needed so that the process can begin at the same time for all APs.

Regards,
loho2027

Offline

 

#4 2016-Sep-14 22:15:25

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

Is it possible for the AP in 802.11 Reference Design to sense whether or not the current channel is being used, and return the value to CPU_HIGH? So, if the AP is on channel 1, and some other AP is also transmitting on channel 1, how would I detect if the channel is taken up?

In CPU_LOW, I did this:

u32 mac_hw_status = wlan_mac_get_status();
int channel_free;
if(mac_hw_status & WLAN_MAC_STATUS_MASK_TX_PHY_ACTIVE) {
channel_free = 0; // not free
}
else {
channel_free = 1; // free
}

However, I found that the channel returns 1 (free) all the time.

Regards,
loho2027

Offline

 

#5 2016-Sep-15 09:30:31

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

Is it possible for the AP in 802.11 Reference Design to sense whether or not the current channel is being used, and return the value to CPU_HIGH? So, if the AP is on channel 1, and some other AP is also transmitting on channel 1, how would I detect if the channel is taken up?

No, CPU High does not have real-time knowledge of medium activity. This is fundamental to the architecture of the 802.11 Reference Design. CPU Low manages medium access, CPU High manages higher level MAC state.

In CPU_LOW, I did this:

u32 mac_hw_status = wlan_mac_get_status();
int channel_free;
if(mac_hw_status & WLAN_MAC_STATUS_MASK_TX_PHY_ACTIVE) {
channel_free = 0; // not free
}
else {
channel_free = 1; // free
}

However, I found that the channel returns 1 (free) all the time.

CPU Low initiates all PHY transmissions, so if you added this code outside the code that starts transmissions it will always indicate the Tx PHY is idle.

Offline

 

#6 2016-Sep-18 18:54:03

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

Hi,

Does the 802.11 Reference Design support 5.0GHz WiFi? If so, how do I change the channel to a 5.0GHz channel, and what channels are available from the 5.0GHz band?

Regards,
loho2027

Offline

 

#7 2016-Sep-19 09:23:02

chunter
Administrator
From: Mango Communications
Registered: 2006-Aug-24
Posts: 1212

Re: Algorithm involving random numbers and time synchronisation

Yes, the 802.11 Reference Design supports the 5GHz channels of 36, 40, 44, and 48. You can provide a channel number to the configure_bss() wlan_exp Python command.

Offline

 

#8 2016-Oct-04 20:45:00

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

I'm trying to detect when a channel is free using carrier sensing. I have the following code:

Code:

if(wlan_mac_low_get_check_channel_free_cmd()) {

u32 mac_hw_status;
mac_hw_status = wlan_mac_get_status();
int chan_free;
if(mac_hw_status & WLAN_MAC_STATUS_MASK_TX_PHY_ACTIVE) {
	chan_free=0;
}
else {
	chan_free=1;
}
xil_printf("chan free:%d", chan_free);
wlan_ipc_msg_t ipc_msg_to_high;
ipc_msg_to_high.msg_id= IPC_MBOX_MSG_ID(IPC_MBOX_CHANNEL_CHECKED);
ipc_msg_to_high.num_payload_words = 1;
ipc_msg_to_high.payload_ptr = (u32*)&chan_free;
write_mailbox_msg(&ipc_msg_to_high);
wlan_mac_low_set_check_channel_free_cmd(0);
}

This code is intended to detect the channel's state and return the information to CPU_HIGH, which I require for implementing a certain algorithm.

I have placed this code in wlan_mac_dcf.c, in frame_transmit. However, I'm not sure where to place it to ensure I get the desired result. If I place the code before the below code, it says the channel is free almost all the time (this might be because it says waiting there is actually rare, and so the channel is mostly free there):

Code:

// Wait for the Tx PHY to be idle
        // Actually waiting here is rare, but handles corner cases like a background ACK transmission at a low rate
        // overlapping the attempt to start a new packet transmission
        do{
            mac_hw_status = wlan_mac_get_status();
        } while(mac_hw_status & WLAN_MAC_STATUS_MASK_TX_PHY_ACTIVE);

And if I place the code before the big 'do' loop (partially shown below), I get the channel is not free most of the time:

Code:

// Wait for the MPDU Tx to finish
        do { // while(tx_status & WLAN_MAC_STATUS_MASK_TX_A_PENDING)

            // Poll the DCF core status register
            mac_hw_status = wlan_mac_get_status();

            // Fill in the timestamp if indicated by the flags, only possible after Tx PHY has started
            if (mac_hw_status & WLAN_MAC_STATUS_MASK_TX_PHY_ACTIVE) {
            	tx_has_started = 1;

            	if(req_timeout){
            		gl_waiting_for_response = 1;
......

This might be because the AP senses its own transmission?

Can you tell me where I should place my code so that it can sense if other APs are transmitting at the same frequency?

Regards,
loho2027

Offline

 

#9 2016-Oct-04 21:29:59

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

Your code is only checking whether the Tx PHY is active. When you place this code in frame_transmit() before the Tx PHY is started, it will report the Tx PHY is idle. If you place this code in frame_transmit() after the Tx PHY is started, it will report the Tx PHY is active. This is the expected behavior.

A busy medium is indicated by Tx PHY activity, Rx PHY activity or Rx power above the physical carrier sensing threshold. The CCA_BUSY bit in the MAC status register reports the MAC core's view of medium state (idle or busy).

More fundamentally, as I explained in post #5 above, CPU High cannot have real-time knowledge of a busy medium. In the current (v1.5) ref design, CPU Low only processes new IPC messages when it is not transmitting or receiving. There is no guarantee that CPU Low will respond to an IPC message with fixed latency. Depending on Tx/Rx activity CPU Low might not respond for an arbitrary time. This is fundamental to the reference design architecture. If your algorithm requires real-time knowledge of medium activity, that part of the algorithm belongs in CPU Low or the MAC core.

Offline

 

#10 2016-Oct-06 17:34:05

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

Referring to Post #2, I'd like to synchronise the access points so it performs a function at the same time. Am I right to believe that without using Python this is not possible with the current implementation, since the timing information inside the WARP board are just the microseconds since boot up?

And even with Python providing the time, is that just for the logs, ie. only looking at the data retrospectively?

Regards,
loho2027

Offline

 

#11 2016-Oct-06 17:54:50

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

If your nodes are members of the same BSS (AP + STAs or many IBSS) their MAC times will be synchronized over-the-air via the timestamp field in beacon frames. This is called the Timer Synchronization Function (TFS) in the 802.11 spec.

Offline

 

#12 2016-Nov-16 20:31:40

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

Hi,

I have the following code in the frame_transmit function in wlan_mac_dcf.c:

Code:

        
if(wlan_mac_low_get_check_channel_free_cmd()) {

			u32 mac_hw_status;
			mac_hw_status = wlan_mac_get_status();
			int chan_free;
			if(mac_hw_status & WLAN_MAC_STATUS_MASK_CCA_BUSY) {
				chan_free=0;
			}
			else {
				chan_free=1;
			}
			xil_printf("chan free:%d", chan_free);
			wlan_ipc_msg_t ipc_msg_to_high;
			ipc_msg_to_high.msg_id= IPC_MBOX_MSG_ID(IPC_MBOX_CHANNEL_CHECKED);
			ipc_msg_to_high.num_payload_words = 1;
			ipc_msg_to_high.payload_ptr = (u32*)&chan_free;
			write_mailbox_msg(&ipc_msg_to_high);
			wlan_mac_low_set_check_channel_free_cmd(0);
		}

I understand that I cannot have real-time channel information using CPU_HIGH, but having one or two seconds latency is fine since I want to determine whether the currently selected frequency channel clashes with another AP's frequency channel. I want the code to detect when it's time to check the channel (using wlan_mac_low_get_check_channel_free_cmd()), checks the channel, then sends a mailbox message to CPU_HIGH to say whether or not the channel is free.

The algorithm I want to implement works like this: it starts off with random frequency channels assigned to each AP, then if it detects a clash of frequency channels, it assigns the channels again with a particular set of probabilities. If there is no clash then the channels should remain the same, and is said to have converged to a solution.

However, I cannot get the channels not to clash, even though in some cases the selection of frequency channels clearly indicate it shouldn't clash. For example, when four WARP boards are in operation, and the frequency channels are 1, 11, 40, 48, then there should be no clash of channels. However, it still detects a clash and switches to another set of frequencies.

I have raised the threshold for carrier sensing in wlan_phy_util.c to a high number (I tried -40dbm) but to no avail. The frequencies still switch. The thing is that it doesn't always sense that the channel is busy. Sometimes it senses the channel is free and so the channels don't change, but they change eventually, even though the channels should be free.

I can think of three reasons:
1) The interference from existing Wi-Fi makes the channels busy. I cannot stop those Wi-Fi networks, but using a Wi-Fi analyser from my laptop the signal strengths appear to be below -50dbm.
2) It is sensing its own transmissions. So whatever channel I choose it will eventually sense itself and switch to another channel according to the algorithm I am using.
3) Related to (2), the code doesn't sense the channel in the way I want it to do. But the channel sensing is used for DCF, so it should work, right? So maybe I have it in the wrong place? But if so, I wonder why it would sometimes detect that the channel is free, and sometimes it detects the channel is busy?

Regards,
loho2027

Offline

 

#13 2016-Nov-17 08:48:04

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

You need to think more carefully about what you mean by "clash". Based on your description above, your algorithm is finished when each AP is tuned to a different channel. Thus, each AP can detect a clash by detecting another AP on the same channel.

The code you posted above does not achieve this. The MAC's CCA (clear channel assessment) status bit indicates the instantaneous state of the medium, quantized to 1 bit (busy or idle). The CCA logic does not filter by activity type (Tx, Rx, energy, NAV), nor does it implement any temporal averaging. You should expect any real wireless medium to transitioning between idle and busy at random due to activity by other devices (other Wi-Fi devices, Bluetooth devices, microwave ovens, etc). This is true even when a given node is not transmitting - an idle node will still observe CCA busy/idle transitions when sensing an active medium.

For your algorithm, doesn't it make more sense to define "clash" as receiving a packet from a peer? If one AP receives a packet from another AP, it's a clear signal that two APs have chosen the same channel and should re-tune.

Offline

 

#14 2016-Nov-17 18:35:56

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

Thanks. So does that mean I should check the list variable 'bss_info_list' in wlan_mac_bss_info.c to see if it's empty or not? If it's empty then no APs are communicating to it, and if it's non-empty then at least one AP is able to connect to it.

How would I lower the sensitivity so that it does not detect APs that are not in close vicinity to the AP? Do I still use wlan_phy_rx_set_cca_thresh from wlan_phy_util.c, or is it not possible to do it?

Regards,
loho2027

Offline

 

#15 2016-Nov-18 08:57:33

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

If your goal is to detect the presence of other APs on the same channel, you should search the bss_info list for those AP's MAC addresses. The bss_info_t structure includes the BSSID (AP MAC address), latest_beacon_rx_power and latest_beacon_rx_time fields. You can use these fields as inputs to your algorithm for detecting co-channel APs. Keep in mind the bss_info list is not reset when the AP changes channels - the list will contain (possibly stale) data about networks on channels the AP was previously tuned to. You can use the high framework wlan_mac_high_reset_network_list() function to remove all bss_info entries if required.

Offline

 

#16 2016-Nov-20 17:47:00

loho2027
Member
Registered: 2016-Aug-16
Posts: 45

Re: Algorithm involving random numbers and time synchronisation

Hi,

Actually I'm not just trying to detect if the APs are on the same channel. If, for example, an AP is on channel 1, and another AP is on channel 2, then there could be interference if the APs are close enough to each other. I want to be able to detect this interference as well.

I'm guessing that bss_info_list does not include APs of adjacent channels?

Also, I found that even though another AP is on the same channel as an AP, it doesn't show up on the bss_info_list all the time. Sometimes it would show that AP, sometimes it doesn't.

Regards,
loho2027

Offline

 

#17 2016-Nov-21 09:06:00

murphpo
Administrator
From: Mango Communications
Registered: 2006-Jul-03
Posts: 5159

Re: Algorithm involving random numbers and time synchronisation

Actually I'm not just trying to detect if the APs are on the same channel. If, for example, an AP is on channel 1, and another AP is on channel 2, then there could be interference if the APs are close enough to each other. I want to be able to detect this interference as well.

This is a harder problem, especially in a real wireless environment with interference from other nodes and devices. The code you posted above is not robust to interference. An instantaneous binary (busy/idle) medium activity measurement isn't a good way to detect whether a specific device is operating on an overlapping channel. You will need to consider better ways to detect this interference. For example, when operating in 2.4GHz you could periodically re-tune the radio to ±1 channels to listen for beacons from  other APs.

Also, I found that even though another AP is on the same channel as an AP, it doesn't show up on the bss_info_list all the time. Sometimes it would show that AP, sometimes it doesn't.

The bss_info list includes an entry for every wireless network from which beacons or probe responses have been received. If an expected network is not in the list, it is because the node has not yet received any beacon/probe packets from that network's AP.

Offline

 

Board footer