Wireless Mesh

Dr_Acula

I've been wanting to build a wireless mesh for some time - I kind of like the idea of redundancy with a swarm of robots or nodes where the system works even if a few stop working, and the system works better if you add more nodes. See at the bottom for a screenshot.
I think the Propeller can do this.

Previously I have started building a few mesh networks, but invariably the code needs changing and it becomes difficult changing code on multiple nodes out in the field. So I've turned to testing it in a simulation first, and have found out all sorts of interesting things.

Let's assume a Propeller chip, and some sort of wireless module. There are many choices and prices one can use. For simplicity, assume a limited range, and that all nodes use the same frequency. Because of the limited range, parts of the mesh can be talking amongst themselves on the same frequency at the same time without interference, and indeed, there is an advantage here to having less range and less power.
The first task a new node has is to find its neighbours. It can send ping messages and over time, build up a table of the nodes it can reach reliably.
The next task is for any node to be able to send a message to any other node. The most efficient way to do this is with the minimum number of hops. To do this, there are several solutions, and a simple one is to build a "routing table" which lists every node's connection and works out the best route.

Well - I tried simulating that and the table got out of control. The number of possible routes goes up something like the factorial of the number of nodes. Fine for 3 nodes with 3x2x1=6 possible paths. Not so good with 20 nodes and 2432902008176640000 paths.
Of course, you can prune the paths, and with a sparse network there still might only be a handful of paths. But the pruning algorithms need a lot of memory and they take time to run. Plus they are kind of complicated to understand http://en.wikipedia.org/wiki/Dijkstra's_algorithm
So after a bit of research I found an intriguing algorithm based on a heat model. It gets a mention on page 3 http://www.ijcst.org/Volume3/Issue5/p15_3_5.pdf
Each node is a heat source, and each produces a different type of heat so you can track the heat from that node. To find a path to that node, simply hop to the hottest nearby node.
I've been playing around with a simulation. Multicast vs unicast packets. Sending nodes to sleep after they have transmitted. Adding a cooling algorithm based on thermodynamics. Working out the optimum number of hops before a packet dies. And the final code is rather simple and certainly something that a Propeller could run.
Take a packet of heat from the source node (joules), take percentage for yourself, then pick a random nearby node and send the rest on to that node. After n hops, the packet dies.

Send these packets out regularly, and over a period of time the nodes all reach the correct temperature such that a message injected at any random node can always find its way to the correct source. There is no routing table, and no need for lots of memory, and each node only works locally. Intriguingly, the heat does not spread out based on distance. It spreads out based on hops, which is what we are trying to optimise for.
Below is the simulation after it has run for a few minutes. The source node is A, and this uses a Black Body temperature scale, where about 6000K is white, temperatures below that are red, temperatures above that are blue. The picture is 1024 pixels wide, and nodes within 300 pixels of each other can talk to each other. All the locations are generated by a random number generator so lots of different configurations can be tested.
Nodes that are many hops away, like L, are the coldest. The fascinating thing is that node I, which is closer to A, is cooler than node T. This is because T has more surrounding nodes, so the packets bounce around more around T. It doesn't matter, because as can be seen from the list of local connections, any message reaching T can go straight to A and bypass I.
The vb.net code is below. Node data is in arrays, but in practice each node would only have its own local information. The simulation only allows transmitting data to local nodes, so there is nothing that can see the whole picture in the same way as this screenshot.
Very sparse networks do start to fail with this system as they form local hotspots and messages bounce around these local maxima. This can be mitigated by decreasing the number of hops before a packet dies, or by increasing the density of the mesh.
I guess the big lesson from this for me is not to try to build a mesh without simulating it fully first. But having simulated it, I can see how it is possible to translate the code over to Spin fairly easily. Need some floating point numbers, and need a simple packet protocol between nodes, probably along the lines of "open comms", "ack", "send data", "close comms".
Anyone here played around with wireless mesh networks?

Imports System.Math ' so can use Log
Public Class Form1
    ' Wireless mesh HEAT protocol
    Dim NodeX(20) As Integer ' x location
    Dim NodeY(20) As Integer ' y location
    Dim Friends(20) As String ' A=node 0, B=node1 etc
    Dim Temperature(20) As Single ' temp in kelvins
    Dim Inbox(20, 4) As Single ' inbox for messages
    Dim SendCounter As Integer
    Dim HopString As String

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim i As Integer
        For i = 0 To 19
            NodeX(i) = Rnd() * 770 ' x - max value so doesn't overwrite the text boxes and buttons
            NodeY(i) = Rnd() * 680 ' y
        Next
        PictureBox1.Location = New Point(NodeX(0), NodeY(0))
        PictureBox2.Location = New Point(NodeX(1), NodeY(1))
        PictureBox3.Location = New Point(NodeX(2), NodeY(2))
        PictureBox4.Location = New Point(NodeX(3), NodeY(3))
        PictureBox5.Location = New Point(NodeX(4), NodeY(4))
        PictureBox6.Location = New Point(NodeX(5), NodeY(5))
        PictureBox7.Location = New Point(NodeX(6), NodeY(6))
        PictureBox8.Location = New Point(NodeX(7), NodeY(7))
        PictureBox9.Location = New Point(NodeX(8), NodeY(8))
        PictureBox10.Location = New Point(NodeX(9), NodeY(9))
        PictureBox11.Location = New Point(NodeX(10), NodeY(10))
        PictureBox12.Location = New Point(NodeX(11), NodeY(11))
        PictureBox13.Location = New Point(NodeX(12), NodeY(12))
        PictureBox14.Location = New Point(NodeX(13), NodeY(13))
        PictureBox15.Location = New Point(NodeX(14), NodeY(14))
        PictureBox16.Location = New Point(NodeX(15), NodeY(15))
        PictureBox17.Location = New Point(NodeX(16), NodeY(16))
        PictureBox18.Location = New Point(NodeX(17), NodeY(17))
        PictureBox19.Location = New Point(NodeX(18), NodeY(18))
        PictureBox20.Location = New Point(NodeX(19), NodeY(19))
        ' need to add labels as well
        Label1.Location = New Point(NodeX(0), NodeY(0) + 20)
        Label2.Location = New Point(NodeX(1), NodeY(1) + 20)
        Label3.Location = New Point(NodeX(2), NodeY(2) + 20)
        Label4.Location = New Point(NodeX(3), NodeY(3) + 20)
        Label5.Location = New Point(NodeX(4), NodeY(4) + 20)
        Label6.Location = New Point(NodeX(5), NodeY(5) + 20)
        Label7.Location = New Point(NodeX(6), NodeY(6) + 20)
        Label8.Location = New Point(NodeX(7), NodeY(7) + 20)
        Label9.Location = New Point(NodeX(8), NodeY(8) + 20)
        Label10.Location = New Point(NodeX(9), NodeY(9) + 20)
        Label11.Location = New Point(NodeX(10), NodeY(10) + 20)
        Label12.Location = New Point(NodeX(11), NodeY(11) + 20)
        Label13.Location = New Point(NodeX(12), NodeY(12) + 20)
        Label14.Location = New Point(NodeX(13), NodeY(13) + 20)
        Label15.Location = New Point(NodeX(14), NodeY(14) + 20)
        Label16.Location = New Point(NodeX(15), NodeY(15) + 20)
        Label17.Location = New Point(NodeX(16), NodeY(16) + 20)
        Label18.Location = New Point(NodeX(17), NodeY(17) + 20)
        Label19.Location = New Point(NodeX(18), NodeY(18) + 20)
        Label20.Location = New Point(NodeX(19), NodeY(19) + 20)

        For i = 0 To 19
            Temperature(i) = 3000 ' start with a middle sort of temp
        Next
        RedoColors()
    End Sub

    Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        ' work out distances to other nodes, if < a certain distance then we are friends
        Dim i, j As Integer
        Dim x, y, x1, y1 As Integer
        Dim d As Single
        Dim DistanceConstant As Integer = 300 ' number of pixels
        For i = 0 To 19
            For j = 0 To 19
                x = NodeX(i)
                y = NodeY(i)
                x1 = NodeX(j)
                y1 = NodeY(j)
                d = ((x1 - x) ^ 2 + (y1 - y) ^ 2) ^ 0.5 ' pythagoras
                If d > 1 And d < DistanceConstant Then ' 0 is myself
                    Friends(i) += Strings.Chr(j + 65)
                End If
            Next
        Next
        ' now list in a textbox
        For i = 0 To 19
            TextBox1.Text += Strings.Chr(i + 65) + "=" + Friends(i) + vbCrLf
        Next
        Timer1.Enabled = True
    End Sub




    'Given a temperature (in Kelvin), estimate an RGB equivalent
    'http://www.tannerhelland.com/4435/convert-temperature-rgb-algorithm-code/

    Private Sub getRGBfromTemperature(ByRef r As Long, ByRef g As Long, ByRef b As Long, ByVal tmpKelvin As Long)

        Static tmpCalc As Double

        'Temperature must fall between 1000 and 40000 degrees
        If tmpKelvin < 1000 Then tmpKelvin = 1000
        If tmpKelvin > 40000 Then tmpKelvin = 40000

        'All calculations require tmpKelvin \ 100, so only do the conversion once
        tmpKelvin = tmpKelvin \ 100

        'Calculate each color in turn

        'First: red
        If tmpKelvin <= 66 Then
            r = 255
        Else
            'Note: the R-squared value for this approximation is .988
            tmpCalc = tmpKelvin - 60
            tmpCalc = 329.698727446 * (tmpCalc ^ -0.1332047592)
            r = tmpCalc
            If r < 0 Then r = 0
            If r > 255 Then r = 255
        End If

        'Second: green
        If tmpKelvin <= 66 Then
            'Note: the R-squared value for this approximation is .996
            tmpCalc = tmpKelvin
            tmpCalc = 99.4708025861 * Log(tmpCalc) - 161.1195681661
            g = tmpCalc
            If g < 0 Then g = 0
            If g > 255 Then g = 255
        Else
            'Note: the R-squared value for this approximation is .987
            tmpCalc = tmpKelvin - 60
            tmpCalc = 288.1221695283 * (tmpCalc ^ -0.0755148492)
            g = tmpCalc
            If g < 0 Then g = 0
            If g > 255 Then g = 255
        End If

        'Third: blue
        If tmpKelvin >= 66 Then
            b = 255
        ElseIf tmpKelvin <= 19 Then
            b = 0
        Else
            'Note: the R-squared value for this approximation is .998
            tmpCalc = tmpKelvin - 10
            tmpCalc = 138.5177312231 * Log(tmpCalc) - 305.0447927307

            b = tmpCalc
            If b < 0 Then b = 0
            If b > 255 Then b = 255
        End If

    End Sub
    Private Sub RedoColors()
        Dim r, g, b As Integer
        ' redo all the colors
        getRGBfromTemperature(r, g, b, Temperature(0))
        PictureBox1.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(1))
        PictureBox2.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(2))
        PictureBox3.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(3))
        PictureBox4.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(4))
        PictureBox5.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(5))
        PictureBox6.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(6))
        PictureBox7.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(7))
        PictureBox8.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(8))
        PictureBox9.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(9))
        PictureBox10.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(10))
        PictureBox11.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(11))
        PictureBox12.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(12))
        PictureBox13.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(13))
        PictureBox14.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(14))
        PictureBox15.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(15))
        PictureBox16.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(16))
        PictureBox17.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(17))
        PictureBox18.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(18))
        PictureBox19.BackColor = Color.FromArgb(r, g, b)
        getRGBfromTemperature(r, g, b, Temperature(19))
        PictureBox20.BackColor = Color.FromArgb(r, g, b)
    End Sub

    Private Sub Button4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click
        SendHeat()
    End Sub
    Private Sub SendHeat()
        ' starts with node A. Send some heat to any nodes that A can contact
        ' each of these nodes waits a random time, then sends on with some of the heat removed
        ' each node only sends once and sends its own temp
        ' so each node needs to record when the heat arrived, how much arrived
        Dim Joules As Integer
        Dim Source As Integer ' from this node
        Dim Hops As Integer
        Source = 0 ' start node - A=0, B=1 etc, always start with A
        Joules = 30000 - Temperature(Source) ' as source gets hotter, send out less energy otherwise overflows
        Hops = 20 ' dies after n hops, optimum seems to be that number of hops roughly equals number of nodes
        Inbox(Source, 0) = Hops
        Inbox(Source, 1) = Joules
        HopString = "Last hop sequence = A"
    End Sub

    Sub ProcessMessage()
        ' each message bounces around until it dies. Each bounce is to a random friend take 20%, send on


        Dim i, j As Integer
        Dim Joules As Single
        Dim Hops As Integer
        Dim MyJoules As Single
        Dim Dest As Integer
        Dim n As Single
        Dim RemainingJoules As Single
        Dim MyFriends As Integer
        For i = 0 To 19 ' check all nodes
            Hops = Inbox(i, 0)
            Joules = Inbox(i, 1)
            If Hops > 0 Then ' message for me, process it, send it to a random friend
                MyJoules = Joules * 0.1
                RemainingJoules = Joules - MyJoules
                Temperature(i) += MyJoules ' add to my temperature
                Inbox(i, 0) = 0
                Inbox(i, 1) = 0 ' clear my values
                Hops -= 1
                If Hops > 0 Then ' send on to a random friend which includes where it might have just come from
                    MyFriends = Strings.Len(Friends(i)) ' how many friends I have
                    ' send based on a random number. Need to be very careful translating between languages
                    ' does rnd() include zero, and does it include 1 (vb.net, yes and no respectively)
                    ' also caution with trancating vs rounding 1.6 truncated is 1 but rounded is 2
                    n = Rnd() * MyFriends
                    n += 1
                    n = Math.Truncate(n)
                    If n < 1 Then n = 1 ' not the best solution but safest to avoid string out of range errors
                    If n > MyFriends Then n = MyFriends
                    n = Convert.ToInt16(n)
                    Dest = Strings.Asc(Strings.Mid(Friends(i), n, 1)) - 65
                    Inbox(Dest, 0) = Hops ' send on to this random friend
                    Inbox(Dest, 1) = RemainingJoules
                    HopString += Strings.Chr(Dest + 65)
                    Label21.Text = HopString
                End If
            End If
        Next
    End Sub


    Private Sub Timer1_Tick(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Timer1.Tick
        Call LoseHeat()
        ProcessMessage()
        RedoColors()
        DisplayTemps()
        SendCounter += 1
        If SendCounter > 30 Then
            SendCounter = 0
            SendHeat()
        End If
    End Sub
    Sub LoseHeat()
        Dim i As Integer
        Dim Ambient As Single = 1000 ' cools down to ambient which is 1000K as this is red on the color chart
        For i = 0 To 19
            Temperature(i) = Temperature(i) - ((Temperature(i) - Ambient) * 0.005) ' cool down a bit each 100ms
        Next
    End Sub
    Sub DisplayTemps()
        Dim i As Integer
        TextBox2.Clear()
        For i = 0 To 19
            TextBox2.Text += Strings.Chr(i + 65) + "=" + Convert.ToString(Math.Truncate(Temperature(i))) + vbCrLf
        Next
    End Sub
    Private Sub Button5_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button5.Click
        Timer1.Enabled = False
    End Sub

    Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
        Randomize()
    End Sub
End Class

kwinn

Your post sounds like a lot of the early papers about networking back when it was known as DARPANET. Lots of interesting theories and findings, a lot of which eventually became part of the internet.

average joe

Very interesting! I've actually developed host-node network topology, loosely based on IPv4. Unfortunately I'm not able to disclose to much about it the current state. I do have plans on releasing a large portion into the public domain when time allows. The design was tested using Xbees (in broadcast mode, essentially turning them into just a wire) although any serial radio could be used. While designing, there had even been some thought regarding changes needed to convert to a mesh network.

What I would LOVE to design something using either the FM or AM tx/rx work others have already done but can't seem to wrap my head around the RF part. I imagine that if you were to set a specific frequency to use (somewhere in the unlicensed bands) it might be possible. Keep in mind I don't plan on using such a device over a very far distance, maybe a few hundred feet? Seems plausible to me, although without a lot of study I'd be very afraid to start playing with this (I live in close proximity to a large airport).

I'm not sure how many people would need functionality that an xbee doesn't have (Digimesh?), although being able to omit the pricey radio and use a few external components to handle the RF while letting the propeller do the rest is very attractive. I could see real promise if a CHEAP transceiver module was used (open-wire) and the propeller was left to handle all the rest (that way the FCC wouldn't have any reason to be knocking at my door).