Secure MultiRobot Management

[Raja]

Hi,
I am currently doing my final year project "Secure mobile Robot
Management" . I have done the theoretical aspects of it till now and
now thinking of coding it .

I would like to code in Python , but i am new to Python Network
Programming .
Some of features of my project are:

1. Each robot can send data to any other robot.
2. Each robot can receive data from any other robot.
3. Every Robot has atleast 1 other bot in its communication range.
4. maximum size of a data packet is limited to 35 bytes
5. each mobile robot maintains a table with routes
6. all the routes stored in the routing table include a ï¬eld named
life-time.
7. Route Discovery Process initiated if there is no known route to
other bot.
8. There is no server over here .
9. every bot should be able to process the data from other bots and
both multicast/unicast
need to be supported.

Assume the environment is gridded mesh and bots exploring the area.
They need to perform a set of tasks (assume finding some locations
which are dangerous or smthing like that).

My main concern is how to go about modifying the headers such that
everything fits in 35bytes .
I would like to know how to proceed and if any links or resources in
this regard. How to modify the headers ? ie. all in 35 bytes .

Thank You,
Raja.

 

[Dennis Lee Bieber]

On 22 Sep 2006 06:14:34 -0700, "Raja" <[email protected]> declaimed
the following in comp.lang.python:

I'm presuming these are using some wireless communication mode --
radio, infrared...

My main concern is how to go about modifying the headers such that
everything fits in 35bytes .

I was about to suggest you study HDLC protocol, possibly as
implemented in Amateur Radio Packet handlers (AX.25 ?) -- add in some
concepts from APRS -- but with only 35 bytes even that is going to be
tricky

Routing tables would be tricky to maintain, since as your robots
move around the routes may change -- how much data do you plan to pass
around just to have "b" send "I can't reach 'c'" messages back to "a"
(and what happens if "b" can't see "a" anymore?)

The APRS method would be something like (node, node, ...; sender;
ID; data):

(a sending): relay2-2, c; a; packetID; message
(b as relay): relay2-1, c; a; packetID; message
(a sees copy): ignore as originator field is self
(c): receives
or
(d as relay): relay2-0, c; a; packetID; message
(b as relay sees copy): count is 0, ignore
(c): receives
or
(e as relay): count is zero, message has expired as "unreachable by
this node"

In AX.25, relaym-n, c, a, b, d, e are all call signs and consume 7
bytes each. relaym-n (and widem-n) is a convention used to reduce the
number of allowed links. Relays beyond 2-2 are frowned upon as they may
cause echo -- digipeaters (the intervening links) don't keep a history
of previous traffic, so a 3-3 could have a packet go from "a" [3-3] to
"b" [3-2] to "c" [3-1] and back to "b" before being dropped.

In defined routing, you'd be encoding (using the second route
above):
(a sending) b, d, c; a; packetID; message
(b relay) *b, d, c; a; packetID; message
(d relay) *b, *d, c; a; packetID; message

The "*" is a bit flag indicating that node x has seen the message
already (when "d" relays it, "b" receives a copy, but with the * on "b"
ignores the packet).

Assuming you can encode the robot IDs in 7 bits (128 robots) and use
the MSB for "seen" flag, you'd need a byte for each allowed relay node
and destination, and one for sender. In the above, that's four bytes
before getting to the packetID.

Using the relaym-n form... Use 7 bits for IDs, and MSB for "relay
ID" -- the relay ID would be something like b'1mmm 0nnn' (which could
encode a relay7-7 <G>).

"packetID" would be something like b'ttss srrr' where tt is a type code
(check HDLC protocol for ful details) -- ack/nak/ack-data/nak-data, and
sss is a modular count of sent packet, rrr is a modular count of last
received packet (for the "connection" -- this is how one end figures out
if a packet needs to be resent; each end can have something like 7
packets "in transit" before it must receive an ACK).

Much of the above is handled by Amateur Radio Terminal Node
Controllers (which combine modem [turn digital to audio tones and back],
the HDLC/AX.25 protocol logic, and radio send/receive switching).
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Dennis Lee Bieber]

<long harangue snipped as I'm talking to myself>

I should probably clarify a few points, as I've got parts of three
separate protocols intermingled above (the previous post).

Pure HDLC, as I recall, has a header that ONLY contains:

From, To, Op/Status code, (I forget if there is a checksum byte?)

where:
From 1 byte address of source
To 1 byte address of destination
Op/Status (1 or 2 bytes, forget which) encodes:
unconnected information
connection request
ready
ready with information
not ready
not ready with information
disconnect

"ready" means "this" end can receive more packets
"not ready" means "stop sending until you receive a ready"
"with information" means a length byte and <length>data bytes are
attached to the packet.
Connection requests and disconnects open/close virtual circuits
(resetting the last sent/last received status bits).
Unconnected information is sort of a UDP broadcast -- there is no
"connection" and no status returns expected.

Amateur packet radio expanded that header structure to allow for
text call signs (FCC requirement for ID needs ASCII call signs in the
packets) so each address becomes 7 bytes (6-byte call: KD6MOG and 1Byte
"node" -- so KD6MOG-15 is different from KD6MOG-10). AND extended to
allow for digipeater routing -- something like an additional six nodes
can be specified by which to route the packet. Digipeaters just receive
packets and, in the next silence, retransmit them, after flagging their
address in the routing header (so they can identify if they've seen the
packet already, or if some node after them has seen it). The status
codes remain the same.

APRS uses ONLY unconnected protocol. It does not create virtual
connections, but also does not require routing tables -- at the cost of
using special RELAY addresses telling any relay nodes to repeat the
packet. If using this transmit method, as I do in my prior example, and
needing a virtual circuit for error checking, one would have to
implement ACK/NAK/time-out and packet counts as part of the information
data.

I should also mention that HDLC is a BIT-synchronized protocol, with
a "0" insert every 5 (or is it 6) bits to avoid having data look like
the synchronization flag... The transmitter sends a series of x7F before
it sends the data packet. Receives look for the 1 bits, and align on the
x7F... Once the data starts, any 0 bit following (5/6?) 1 bits is
dropped. Collisions (two transmitters starting up at the same time) is
handled by timeouts on lack of a ready/not ready count, with a resend of
the data -- or for unconnected... Just ignored...

So... You do NOT want to code the HDLC protocol in Python (I'm not
even sure if common BASIC Stamps have enough program memory to code the
transmit/receive logic -- possibly the bit alignment send/receive can
fit a BASIC Stamp, with the reconstructed bytes handled by a higher
level processor in Python.

Also note that HDLC is an asynchronous packet protocol... so the
receiver operation has to be running all the time to catch any packet
(and the transmit side needs to know when the air is clear before trying
to send). Sounds like a need for threading, at the least. It will be a
layered system:

Application

Robot Protocol (any protocol you put in Information packet)

HDLC Protocol (connection/status/addressing)

HDLC Radio Control (synch flags, bit stuffing on transmit,
reconstruct on receive, silence before send) [This may be subdivided
into two parts -- Byte level packet handling, with serial communication
to the bit-level radio modem]

-=-=-=-=-=-

HDLC-RC, synchs and reconstructs a byte level packet. This packet
would be passed to HDLC-P (somehow this is getting bytes, and would
likely use Queue to relay the full packet to the Protocol layer).

HDLC-P would pull a packet off the Queue, check the last received
status (if connected) and, if needed, back up to an early send packet
and start sending from that (3 bits, up to 8 packets can be sent before
a confirmation of receipt -- if the last-received count doesn't
increment, the sender has to resend from the appropriate packet; so
HDLC-P needs to use a circular buffer of 8 send packets)[a dumb receiver
would drop any packet that wasn't the immediate next packet expected; a
smart one would hold the packet while sending expected count for the
missing packet -- then insert the missing packet into the buffer before
processing it]. For received information packets, the application data
is extracted and passed (another Queue) to the RP level.

Downward data would be passed from RP to HDLC-P via a Queue, HDLC-P
would take these data packets and append them to status (connected mode)
packets, and pass those (another Queue) to the HDLC-RC.

You DO NOT WANT interrupts occurring in the actual radio control
level, just a fairly tight loop of:

if have_outbound_packet and radio_silent
send synch
send packet with bit stuffing
send end packet marker
if not radio_silent and not synched
look for synch pattern
while synched
collect bits and parse into bytes (remove stuffed 0s)
if full byte
send over serial port
if end_packet_marker
break
collect byte for out going packet (should use RTS/CTS on serial with
timeout)


--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/