ZigBee for IoT

The ZigBee and Z-Wave short-range wireless technologies are used for remote monitoring and control. However, their specifications and applications are different. Both technologies are ideal for home-area networks (HANs), which is becoming an in.

Differences between ZigBee and Z-Wave:

Technology	Frequency	Modulation	Data Rate	Range	Applications
ZigBee	902 to 928 MHz (Americas and Australia)2.4 - 2.483 GHz (ISM)	BPSK (900 MHz band) or OQPSK (2.4 GHz band)	250 kbps	10 m	Home Automation, Smart Grid, Remote control
Z-Wave	908.42 MHz	GFSK	9.6/40 kbps	30 m	Home Automation, security

ZigBee

It is ratified in the IEEE’s 802.15.4 personal-area network (PAN) radio standard. ZigBee is an open wireless standard from the ZigBee Alliance. The IEEE 802.15.4 standard provides layer 1 (physical layer, or PHY) and layer 2 (media access controller, or MAC) of the network, while the ZigBee stack software provides the network and application layers.

The Zigbee protocol is designed to communicate data through hostile RF environments that are common in commercial and industrial applications.

Zigbee protocol features include:

• Support for multiple network topologies such as point-to-point,
• point-to-multipoint and mesh networks
• Low duty cycle – provides long battery life
• Low latency
• Direct Sequence Spread Spectrum (DSSS)
• Up to 65,000 nodes per network
• 128-bit AES encryption for secure data connections
• Collision avoidance, retries, and acknowledgments (CSMA/CA)

ZigBee Physical Layer

ZigBee PHY operates in various bands, but the most common one is in the 2.4 GHz band. It uses offset quadrature phase-shift keying (OQPSK) that transmits two bits per symbol. In 900 MHz band, it uses BPSK for modulation.  The radio uses DSSS for digital streaming.

There are three (3) kind of devices in ZigBee:

1. ZigBee Coordinator (ZR)
2. ZigBee Router (ZR)
3. ZigBee End Device (ZED)

Hot skills in Embedded and IoT

Based on my observation in the job market, the following skills are currently in demand in embedded systems surrounding IoT development:

1. 802.11 (WiFi)
2. Bluetooth, especially Bluetooth 4.0 + Low Energy (BLE) or newer
3. Zigbee (IEEE 802.15.4)
4. Z-Wave: Based on ITU G.9959 (PHY) and Z-Wave Application layer
5. Bonjour (mDNS/DNS-SD)
6. SSDP (Simple Service Discovery Protocol)
7. OCF (Open Connectivity Foundation's uPnP Device Control Protocol)
8. TCP/UDP
9. TLS (Transport Layer Security)
10. CoAP (Constrained Application Protocol; RFC-7252)
11. HTTP, especially RESt API
12. MQTT (Mosquitto)
13. MultiThread
14. Websockets
15. RESTful (Representational State Transfer) architecture
16. Rust (Rust is a programming language that’s focused on safety, speed, and concurrency)
17. Jenkins
18. XML
19. LWM2M
20. SQS
21. AMQP
22. Kafka
23. AWS (Amazon Web Service)
24. Microsoft Azure
25. I²C
26. SPI
27. Asynchronous serial/UART programming
28. Linux Kernel and Driver development
29. 
    

Pointer to certain address in memory

In embedded system where we are working with microcontroller, many times we find a scenario where we need to access a memory-mapped register in the MCU.  How do we do that in generic way (for example with GCC compiler)?

The answer is to write it like below:

volatile <type> *<varname> = (<type> *)<address>

For example:

#include <stdio.h>

volatile char *var = (char *)0x1000;

int main()
{
    if (*var != 0)
        puts("NOT NULL!");
}

rendered into x86 assembly (64-bit Intel CPU) as:
...
...
.LC0:
        .string "NOT NULL!"

main:
movq var(%rip), %rax      # rax = address of var
movzbl (%rax), %eax         # eax = *var
testb %al, %al
jne .L9
xorl %eax, %eax
ret
.L9:
pushq %rax
movl $.LC0, %edi
call puts
xorl %eax, %eax
popq %rdx
ret

...
.LCOLDE1:
.section .text.startup
.LHOTE1:
.globl var
.data
.align 8
.type var, @object
.size var, 8
var:
.quad 4096           # or 0x1000

Deleting duplicate entries and sorting the rest

I learned an interesting (and very easy) way to remove duplicate entries as well as to sort them. Basically, in C++ it is achieved by creating a new set and initialize with values from the vector.  We shift all the hardwork to the std library to do this.

#include <iostream>
#include <vector>
#include <set>


void print(std::vector<int> &v)
{
    std::cout << "[";
    for(std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::cout << *it << ",";
    }
    std::cout << "]" << std::endl;
}


void print(std::set<int> &v)
{
    std::cout << "{";
    for(std::set<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::cout << *it << ",";
    }
    std::cout << "}" << std::endl;
}



int main()
{
    int inits[] = {1,10,3,2,2,4,4,5,6,7,8,8,9};
    std::vector<int> vec(inits, inits + sizeof(inits)/sizeof(inits[0]));
    print(vec);
    std::set<int> ves(vec.begin(), vec.end()); // both sorted & unique already
    print(ves);
}

Finding missing sequential numbers

Say you have an array with integer sequential numbers in it, but there are missing numbers in it.  How to find what are those numbers?  Assume the array is already sorted ascendant.

Solution
On the Internet, I found cases where there is only one number missing and the approach is to do sum of the numbers and verify if the sum S equals to n*(n+1)/2.  S(n) = n + (n-1) + (n-2) + .... + 0.  If not equal, then difference is equal to the missing number, because S + missing number must be = n*(n+1)/2.

def MissingSingleNum(A):
    sum = 0
    n = A[len(A)-1]
    for i in A:
        sum = sum + i
    computed = n*(n+1)/2
    if sum != computed:
        return computed - sum
    else:
        return "None"

A = [1,2,4,6,7,8]
MissingSingleNum(A)

Some weaknesses of the above algorithm it cannot find more than one missing number and numbers in the array should not be negative.  So in case of [-3,-2,-1,0,1,2,3,5], the computed sum is 8*(8+1)/2 = 36 (remember n is = number of elements in the array), where it is supposed to be 5, and the missing number is 4.  The same issue for A=[0,1,2,4,6,7,8] where [3,5] are missing, the algorithm cannot find that either.

To solve multiple missing numbers, we cannot use the above approach.  Basically we need to classify the cases.  Say we have A = [-2, 0, 2, 6, 12]
By looking at it, we know for the range [-2..12], the missing numbers are [-1,1,3,4,5,7,8,9,10,11].

One approach is, we scan from the lowest number to highest number and see if there are missing sequential numbers. Because we already know the array is sorted, we scan a range from A[0] to A[len-1] and check against a dictionary we build (see below).  The dictionary (or hash table) is very fast, it's only O(1) when the numbers are unique.

def IsExist(d,k):
    try:
        d[k]
        return True
    except:
        return False


def MissingNumbers(A):
    n = len(A)
    miss = []
    d = {}
    j = 0
    for e in A:
        d[e] = j
        j = j+1

    for i in range(A[0], A[n-1]):
        try:
            if not IsExist(d,i):
                miss.append(i)
        except:
                pass
                
    return miss


Test:

A[] = [0, 2, 4, 5, 6]
Missing numbers: [1, 3]

A[] = [-2, 0, 5, 16]
Missing numbers: [-1, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

A slightly better way or an improvement of above code is the factthat we can use <array>.index(value) to check if a value exists in the array (so no need to use dictionary).

def MissingNumbers(A):
    n = len(A)
    miss = []

    for i in range(A[0], A[n-1]):
        try:
            if A.index(i):
                pass
        except:
                miss.append(i)
                
    return miss

Finding two items in array that has sum of s

Suppose we have an array A with n items (A[0]...A[n-1]) and we want to find two members in the array (must be unique items, e.g, cannot be A[i] + A[i]) that has the sum of s.

With Brute-Force approach, we actually scan the array from i=0 to n-1 and check if the sum with its next item equals s.

For example, a Python code like below:

#!/usr/bin/python3

A = [-1, 3, 5, 6, -2, 10, 7, 9, 8, 4]

s = int(input("Enter the wanted sum: "))

# brute-force

for k in range(len(A)-1):
    for l in range(k+1,len(A)):
        if A[k] + A[l] == s:
            print("Found it: A[%d]+A[%d] = %d" % (k,l,s))
            print("\t%d+%d = %d" % (A[k],A[l],s))
            break


The problem with this approach is obviously not optimal (the complexity is O(n²)).

A better method is if we don't need to walk through the array second time (the second loop).  We still need to walk through each item in the list, though.

def ArrayToDict(A):

    h = {}

    for i in enumerate(A):

        key = i[1]

        val = i[0]

        h.setdefault(key, []).append(val)

    return h

def IsValExist(H,k):
H = ArrayToDict(A)
for enum in enumerate(A):

    ret = True

    try:

        H[k]

    except:

        ret = False

    return ret

    i = enum[0]

    v = m - A[i]

    if IsValExist(H,v):

        for iv in H[v]:

            if iv != i:

                print("GOT IT: A[%d](%d) + A[%d] (%d) = %d" % (i, A[i], iv, A[iv], m))

With this approach, the complexity is only O(n) (assuming only very few key duplicates, if any, in the hash/dictionary).