Bit of a tough chunk of coding last night, mostly because I misdiagnosed a problem and ended up spending more time trying to insure that I was passing arrays than I needed to.

So the event queue needs to detect collisions. Not in a PDES sort of way, but in the simulator itself. Two nights ago, I realized that packets don’t have an explicit receiver, so my strategy for detecting collision was going to have to be rewritten. Last night, I rewrote it.

So in the final product, two packets only collide if they are using the same channel. So far, I haven’t implemented channelization, I’m just building a basic simulation framework, so the method collides_with in is a one liner:
def collides_with(pak) return true; end. The code in the Packet Queue is a little more complex. The Problem is this: The queue goes through the following steps

1. Get the first packet from the queue, and all following packets with the same time stamp
2. For every packet, get the neighborhood of the sender
3. Compare packets
4. If two packets collide, remove any common nodes from the neighborhood associated with that packet
5. Send the packets to the remaining nodes

And that collision detection part is tricky.

Right now, my code looks something like this:

def collision_detect(hoods, moments)
   colliders = []
   for k in 0..moments.size-2
     for i in k+1..moments.size-1
       if moments[k].will_collide(moments[i])
         colliders.push(hoods[k] & hoods[i])
         hoods[i] = hoods[i] - hoods[k]
       end
     end
     if !colliders.empty?
       colliders.flatten!
       colliders.uniq!
     end
     hoods[k] = hoods[k] - colliders
     colliders = []
   end
end

But I don’t think that is working the way I want it to, because my tests are coming back with no calls to any transceivers. This is a frustrating piece of code to test… partially because it doesn’t belong in this class, but mostly because I’m not sure when Ruby is going to return an empty array and when it is going to return nil. And this matters.

Something I noticed about that algorithm versus that code, though. So much of the algorithm is “Get some list, and do something to every item on the list” and yet the code contains no Array.map calls. So obviously I’m doing this wrong. And LISP might be a better language for event simulation than Ruby, because it might be easier to treat anything at all as an event, since all LISP code has the same syntax.

Well, it was inevitable. First major conceptual mistake in SimpleHoc discovered last night.

For some reason, I was giving packets explicit receivers. This is wrong. Packets should have explicit senders, and, later, explicit destinations, but the immediate receiver is handled by the underlying channel selection event queue algorithm. Anyway, as a result of this, I was finding the neighborhood of local nodes, and then putting a packet in the event queue to be sent to all of those nodes.

This is a problem. It’s mostly a problem because the neighborhood of a node might change between the time the event is queued and the time that the event occurs. Unlikely with my sim, because it’s single threaded, but possible if I want to take this code over to the cluster and run a distributed/parallel version. Of course, I probably don’t want to write that in Ruby anyway…

Actually, I might. Maybe this is a rails app waiting to happen. That would be cool, and very appropriate for HiPC.

Anyway, I ended up realizing that what I want is to put a single packet on the queue, then let the queue choose who gets the packet when the packet is sent. I’m only partway through that rewrite. I hate running out of steam in the middle of a function. You just know you’ve lost an hour at least rebooting the brain, but as your body slows down, you hit this point of diminishing returns. Oy.

Anyway, I also added 200 lines of case statements, but I’ll spare you a look at the StateMachine module. There has to be a better way to do that.

mercurial repos: http://simhoc.hg.sourceforge.net:8000/hgroot/simhoc

5:42 AM, and I have one test still to write. I need sleep. The last 4 hours or so have been pretty productive. No code to show today, except this test:
def test_get_neighbors
@neighborhoods = []
for k in @myfactory.hocnode_list
for j in @myfactory.hocnode_list
if k.get_neighbors.include?(j)
assert(j.get_neighbors.include?(k), “Not included”)
end
end
end
end which tests the symetric property of neighborhoods.

A lot of time today looking at the default conditions for creating various objects and chasing sytax errors. Ick.

As always, source code to be found here: http://simhoc.hg.sourceforge.net:8000/hgroot/simhoc

I’ve been fighting a migraine all day, a problem I thought was more or less behind me with my new medication. But 8 hours and 10 cups of coffee later, it’s gone. It’s actually been coming and going the whole time, which is a huge improvement.

So it’s 4AM and I’m headache free. Oy. Anyway, new code for today, collision detection. My thinking here is this: I have this event queue for my Discrete Event simulator. Some of the events collide, for example, events that happen at the same time and place would collide.

So… the new run_sim code looks like this

def run_sim(endTime)
until @pheap.empty? || @pheap.first.timestamp > endTime
@moment = @pheap.first.timestamp
@momentlist = []
puts @moment
until @pheap.empty? || (@moment != @pheap.first.timestamp)
@momentlist.push(@pheap.shift)
end
collision_detect(@momentlist)
until @momentlist.empty?
@pak = @momentlist.shift
@pakList = @pak.receiver.receive_packet(@pak)
until @pakList.empty?
put_packet(@pakList.shift)
end
end
end
end

Where we pull all the events with the same time stamp off the head of the queue and then check them for collision with the routine collision_detect.

def collision_detect(paks)
@l=paks.length-1
@colliders = []
for k in 0..@l-1
for i in k+1..@l
if paks[k].collides_with(paks[i])
@colliders.push(k)
@colliders.push(i)
end
end
end
@colliders.uniq!
@colliders.sort!
@colliders.reverse_each{ |x| paks.delete_at(x)}
end

Things that bother me about this piece of code… I don’t think this is very rubyist. It seems really clunky to nest those for loops. I miss my applescript and Lisp lists, where instead of writing k+1..[].length I could just say rest. On the other hand, the [].uniq! method indicates to me that there is a way to do this that is more… rubyist. Whatever that really means. It also bothers me that this code is somewhere on the order of n²/2, potentially. Add up enough steps like that and you could be in real trouble.

So that chunk of code calls this one:
def collides_with(pak)
if @receiver.ident == pak.receiver.ident
return true
else
return false
end
end

Which is basically a stub at this point. Really, the question is whether one hoc_node is in the neighborhood of another, but to find that out I need a neighborhood method and I haven’t written it yet.

slow coding day today. I implemented my event queue, which is important, and I made some changes on the paper as well, although since those are mostly formatting I’m not going to post.

One thing I’ve decided is to stop using Netbeans. Netbeans is slow, and it focuses on code/structure control at the expense of text control. Text control is important, so I’m trying to use emacs + terminal, the same toolset I use for writing LaTeX. This is working out pretty well, no more spinning wheels of death.

Also, set up a mercurial repository on SF, just for fun. I generally use subversion, but figured I’d try something a little different. You can check out the code

http://simhoc.hg.sourceforge.net:8000/hgroot/simhoc

there. So, pretty busy day. I spent a lot of it writing little tests, though, to see how the self keyword operates in Ruby. I don’t know if I have the full grasp of when new objects are created and when old objects are referenced, but I do have enough of it to know that I can pass an object as a parameter to its members, although possibly I don’t need to.

I know I’m doing baby Ruby, barely scratching the surface of what I could be doing. But I just want to prototype this thing and move on, and I think it’s moving pretty quickly.

class PacketHeap
attr_reader :pheap
def initialize (heap = [])
@pheap = heap
end
def run_sim(endTime)
until @pheap.empty? || @pheap.first.timestamp > endTime
@pak = @pheap.shift
@pakList = @pak.receiver.receive_packet(@pak)
until @pakList.empty?
put_packet(@pakList.shift)
end
end
end
end


To Do: Add a collision detector stud, add a neighborhood gathering routine, add the Hocnode list to the Hocnode factory, build state transitions, trigger state transitions.

So, for some reason, at about 11 of the clock last night I decided to rewrite my entire simulator in Ruby. You would think I would be regretting this, the loss of months of work, but I’m not. Overnight I have most of the basic structure together, and frankly, the language is just so much nicer to work in.

Java is huge, daunting, with its acres of libraries. If you know it, I’m sure that it is wonderful, but that strong typing thing annoys the hell out of me and slows me down.

Ruby seems to be a good prototyping language. I mean, I built a priority queue (probably not a very good one) in three lines of code. And all my code, right now, is tested and good to go. I don’t know, we’ll see how I feel after some sleep. But so far, so good.

The priority queue is below… there’s a type check, but the big thing is that these are the only ways to access this array. So it’s a priority queue because you can’t add anything to the array without sorting it, and you can only remove the top object.

On the other hand, I have no idea how it is stored, so… yeah. Probably, this would be faster if it were a fibo heap or something, but like I said, I’m prototyping.


def put_packet(somePacket)
if somePacket.kind_of?(Packet)
@pheap.push(somePacket)
@pheap.sort! { |a,b| a.timestamp <=> b.timestamp }
return true
else
return false
end
end

def get_packet
return @pheap.shift
end


So the web site doesn’t look right to me. First, there’s this theme, this blog. This blog does not look like the rest of the site, and I think I can fix that pretty easily if I choose to.

Second, on the main site, the dynamic navigation menu doesn’t do what I want it too, exactly. It loads dynamically, but it really, it’s just loading html based on some previous hooks. It isn’t writing HTML based on some information.

So that’s what I want to work on next, setting up the navigation bar so that it is truly dynamic. And I think the way to do this is several hash table of “page” objects and an ID tag that accesses it. The page objects can contain the routines that explain how they are displayed in various settings, and then I just need a for loop that goes throught them and generates the actual code. The idea being that depending on what page you are on, you will see different navigation, and the current page should be highlighted in the animation.

More on this as time expires.

Or, if you want to register, you can tell me why this approach won’t work.

Added a section to my ad hoc networking paper, explaining how the core needs of the network are being met.

3.2.3 Behavior

Each node starts up with its data transceivers in the Idle state and its control transciever in the Hungry state. From that point forward, the state transitions should insure that the network is connected, colored, and stable. As mentioned in section 1.1, there are three basic rules that must be satisfied for the distributed algorithm to work. This section describes how those rules are met.

When a node chooses to create a link, or send an invitation on a link, that channel is preemtively removed from the list of available channels. That is, a channel is assume to be used if the node is negotiating the use of the channel. Remembering that a negotiation occurs betweeen an invitor and a respondent, and that channel open requests are served sequentially, we know two things.

First, a node can only have one active negotiation occurring for a channel at any time, because the first initialization of a negotiation preemptively reserves the channel. Second, successful negotiations reserve the channel, so no future negotiation will occur for that channel until it is released. Therefore, a node will only use a specific channel to form a single link.

This rule is satisfied in two ways. First, the channel availability list is the difference between the set of all channels and the union of the channels being used by a node and all of its neighbors. Using the notation N_x to indicate “the neighborhood of x”, consider three sets of nodes, A, B, C , where ¬ ∃ n ∈ A | n ∈ N_C, ∀ n ∈ B, n ∈ N_A ∧ n in N_C. The rule should be that if an node in B is using a channel for communication with any node in A ∪ C, than no node in A ∪ C can use that channel for any communication at all (even with a node in D where ∀ n ∈ D, n ∋ N_B. As defined, the channel availability list assures this by removing all of the channels used by B from the availability list of all nodes in A ∪ C.

However, it is possible that a situation will occur that will allow two nodes that are already using a channel to conflict. For example, if a node in A changes position such that it joins set B, conflict can occur with C. In this case, the transciever rules handle the conflict. The node that first notices the conflict will recieve a packet on a channel that it is using that is not meant for it. In this case, it will interpret that packet as a packet x, and the state transfers from Table 3 occur. Briefly, that transciever will move from the Cstate to the Fstate, and attempt to find a new channel to share with its partner.

By preempting conflict in channel negotiation through sharing of channel usage information and preemptive dropping of conflicting channels, conflict should be resolved before it becomes a problem.

Abstract:

We study the problem of structuring an Ad Hoc network as a
collection of persistent node to node links, utilizing a collection
of resources such as channels or time slots to determine which node
pairs can communicate. A new algorithm, Starving Artist, is
presented to solve the link based channel assigment and maintenance problems in a distributed fashion.

1  Introduction

1.1  Problem Definition

An ad hoc network can be viewed, without loss of generality as a Unit
Disk Graph.[6] The potential for traffic collisions exist
whenever two nodes in proximity to each other attempt to transmit
using the same channel.¹ The potential for collisons can
be modeled as an edge coloring problem in which each channel is
assigned a color and the the colors distributed on the graph.

A formal discussion of the link based channel assignment problem can
be found in [2]. Briefly, the formulation is a vertex
coloring on some subgraph of the square of the Line Conflict Graph of
the Unit Disk Graph. A transformation of this coloring and link
selection back to an edge conflict coloring will give us the Network
Graph.

This global view of the problem is formally interesting. However, for
the purposes of a distributed algorithm, it is more helpful to analyze
the ad hoc network in terms of characteristics and rules that can be
identified from the individual nodes.

If there are n nodes in the ad hoc network, it can be viewed as a
set of n neighborhoods, where a node v has a neigborhood of nodes
(v₁, v₂, … v_n) within it’s broadcasting range. Each node has
available to it some set of channels K, and attempts to
form persistent links to other nodes in its neighborhood using these
channels pursuant to the following rules:

1. 
   A node should not use a channel for more than one link.
   
2. A node should not use any channel that is being used by one of
   its neighbors unless it is linked to that neighbor on that channel.
   
3. No node should have a disconnected neighbor.
   

A distributed algorithm that follows these rules will also solve the
distance 2 coloring problem for the network graph, allocating channels
in such a way that conflict free communication can take place over
persistent two-way links.

2  Related Work

Ten recent papers in Channel Allocation that should be reviewed
briefly, ranging from 2005 to
2008.[10, 5, 8, 4, 2, 3, 11, 9, 7, 1]

3  Algorithm

3.1  Assumptions

The Starving Artist algorithm has several global and structural
assumptions that are important to understanding its behavior.

3.1.1  Global Assumptions

One global assumption is that the algorithm is running on independent
devices that share a wireless communication medium. For example,
mobile phones using bluetooth connections, or laptops with wireless
cards. Each device is therefore a node n in the network N. Each
node n_i has a neighborhood N_i of nodes that it are in its
broadcast range. This neighborhood is assumed to be symetrical, that
is, ∀ n₀, n₁ ∈ N, n₁ ∈ N₀  ⇐⇒ n₀ ∈ N₁.

It is assumed that there is a Channel structure for the network, that
is, there is some resource such as radio frequencies or time slots
that can be assigned to nodes, noted as K. Any node is
assumed to have potential access to any Channel for the purposes of
listening or broadcasting. We also assume that there are enough
channels available to connect the network.

3.1.2  Structural assumptions

One channel is reserved for control communication. Control
communication is broadcast from a node to its entire neighborhood. All
nodes are assumed to be listening to the control channel at any time
that they are not broadcasting.

Starving Artist assumes that each node can form at least two data links, that is, it
can commit to transmitting packets to and from at least two other
nodes using two separate channels. Again, a node is assumed to be
listening to each of its channels at any time that it is not
broadcasting.

Starving Artist also assumes that each node has some unique identifier.

These structural assumptions can be made without loss of generality
because there do exist schemes that meet these criteria.[7]
Starving Artist is a general purpose approach that will need
modification to fit into a specific channelization scheme.

3.2  Starving Artist

3.2.1  Overview

We model the algorithm using modified finite state machines, similar
to DEVS models as defined by Ziegler et al.[12] There are two
basic machines, the Node machine and the Transceiver

machine. Node machines act as containers for a group of Transceiver
machines, routing messages between them and keeping a global table of
the neighbor machines and relevant channel usage. Transceiver machines
handle communication between Nodes, broadcasting and receiving
messages using the wireless medium. To meet the assumptions in the
previous section, each Node machine acts as a container for at least
three Transceivers.

There are two kinds of Transceiver machines, Control and Data. Control
Transceivers communicate on a single channel in broadcast
fashion. Data Transceivers communicate with one other Data Transceiver
on a different node using a single channel.

The general idea is that each node maintains a list of open channels that it can communicate on. If the node has open channels and open data transceivers, it will attempt to form partnerships with it’s neighbors by sending an invitation on the control channel to share a data channel. The neighbors that can share that channel will respond to the invitation on the control channel (using some random delay) and prepare to receive a confirmation message from the original inviting node. The inviting node sends its confirmation with the ID of the first node that it receives a response from. All other nodes on that channel will react to the confirmation by marking that channel of their lists of open channels.

3.2.2  Machine Definition

The transceiver machines are modeled as a tuple
M=(Σ,Γ, S,s₀,δ,τ,S_F, ρ) where Σ is an
input/output alphabet, Γ is a set of channels, S is a set of states of which one (S₀) is initial and 0 or more (S_F) are final, δ is a transition function between those states, rho is a set of ports and τ is a timer. A state change occurs when the transceiver receives a packet, either from the node or from another transceiver on some port. At that point the transceiver will send a packet on a channel by an output port, then change its state S and channel, then reset its timer. This transition function is shown in Equation 1.

Table 1 contains the complete alphabet for the transceiver machines. This is actually two alphabets, an alphabet for the Data machines and the Control alphabet. Each symbol is bound to one of the two ports that a transceiver has, eliminating the need from ρ in the transition equation. Table 2 contains a list of all of the states for transceivers. Table 3 shows all the possible transitions for each State.

---

Data Alphabet
Σ	meaning	ρ	Σ	meaning	ρ	Σ	meaning	ρ
e	invitation received	1	r	invitation issued	1	s	RSVP	1
a	RSVP acceptence	1	x	conflicting transmission	1	f	change channel	1
t	timeout	2	p	ping	1	m	standard message	1
k	kill state	1	g	gnip	1	y	check state	2
d	channel change	1	w	m from node	2
Control Alphabet
o	1 transceiver open	2	i	invitation	1	b	all transceivers used	2
q	no colors available	2	u	update color lists	1	h	2+ open transceivers	2
l	some colors available	2	e	invitation received	2	t	timeout	1
n	send updated list	2	z	check my state	2

Table 1: Transceiver Alphabets

---

---

Data States
Symbol	meaning	Description
I	Idle	Not communicating
R	Invitor	Listening for a response to an invitation
E	Invitee	Listening for response to an RSVP
C	Committed	Linked to another node’s transciever on a channel
U	Uncertain	Waiting for confirmation that it’s partner is still live
F	Conflicted	Waiting for Partner for acknowledge channel change
Control States
Symbol	meaning	Description
H	Hungry	2+ open data transcievers
D	Sated	1 open data transciever
B	Bloated	0 open data transcievers
A	Painted	Hungry with no open colors
Q	Laquered	Sated with no open colors
V	Varnished	Bloated with no open colors

Table 2: Transceiver States

---

---

Idle	e× I sΓ→ EΓ	Invitor	k × R y→ I	Invitee	k × Eτy→ I
	r × I∞y→ R		s × R a→ C		a × E y→ C
					m × E w→ C
			t × R y→ I		t × Eτy→ I
			x× R y→ I		x × Eτy→ I
Committed	m× C w→ C	Conflicted	m× F w→ C	Uncertain	m× U w→ C
	p × C g→ C		p × F g→ C		p × U g→ C
	x × C f→ FΓ		x × F f→ FΓ		x × U f→ FΓ
	t × C p→ U		t × F y→ I		t × U y→ I
	k × C y→ I		k × F y→ I		k × U y→ I
	f × C pΓ→ CΓ		f × F pΓ→ F		f × U p→ C
	w × C m→ C		w × F m→ F		w × U m→ U
	d × C → C		d × F y→ F		d × U y→ U
	g × C p→ U		g × F f→ FΓ		g × U y→ C
Hungry	u× H n→ H	Sated	u× D n→ D ′	Bloated	u× B n→ B
	n × H u→ H		n × D u→ D		n × B u→ B
	i × H e→ H		i × D e→ D		i × B → B
	h × H → H		h × D → H		h × B → H
	o × H → D		o × D → D		o × B → D
	q × H → A		q × D → Q		q × B → V
	l × H → H		l × D → D
	b × H → B		b × D → B
	t × H i→ H
Painted	u × A n→ A ′	Laquered	u× Q n→ Q ′	Varnished	u× V n→ V
	n × A u→ A		n × Q u→ Q		n × V u→ V
	i × A z→ A		i × Q z→ Q		i × V → V
	o × A z→ Q		o × Q z→ Q		o × V z→ Q
	h × A z→ A		h × Q z→ A		h × V h→ A
	l × A z→ H		l × Q z→ D		l × V z→ B
	b × A z→ V		b × Q z→ V
	q × A z→ A		q × Q → Q
For simplicity, a Γ superscript in either a transition message or resulting state indicates a needed channel change. All timers are assumed to be reset to zero, and any state which does not accept a t message runs its timer to ∞.

Table 3: Transition Functions

---

References

[1]

A. Akella, G. Judd, S. Seshan, and P. Steenkiste, “Self-management in chaotic
wireless deployments,” in MobiCom ’05: Proceedings of the 11th annual
international conference on Mobile computing and networking.1em plus
0.5em minus 0.4emNew York, NY, USA: ACM, 2005, pp. 185–199.

[2]

J. Avonts, N. Van den Wijngaert, and C. Blondia, “Distributed channel
allocation in multi-radio wireless mesh networks,” Computer
Communications and Networks, 2007. ICCCN 2007. Proceedings of 16th
International Conference on, pp. 939–944, Aug. 2007.

[3]

A. Chia-Chun Hsu, D. Weit, and C.-C. Kuo, “A cognitive mac protocol using
statistical channel allocation for wireless ad-hoc networks,” Wireless
Communications and Networking Conference, 2007.WCNC 2007. IEEE, pp.
105–110, March 2007.

[4]

T. Dasilva, K. Eustice, and P. Reiher, “Johnny appleseed: wardriving to reduce
interference in chaotic wireless deployments,” in MSWiM ’08:
Proceedings of the 11th international symposium on Modeling, analysis and
simulation of wireless and mobile systems.1em plus 0.5em minus
0.4emNew York, NY, USA: ACM, 2008, pp. 122–131.

[5]

L. Gao, X. Wang, Y. Xu, and W. Chen, “Distributed multi-radio channel
allocation in multi-hop ad hoc networks,” Communications, 2008. ICC

’08. IEEE International Conference on, pp. 3156–3160, May 2008.

[6]

F. Kuhn, T. Moscibroda, and R. Wattenhofer, “Initializing newly deployed ad
hoc and sensor networks,” in MobiCom ’04: Proceedings of the 10th
annual international conference on Mobile computing and networking.1em plus 0.5em minus 0.4emNew York, NY, USA: ACM Press, 2004, pp.
260–274.

[7]

X. Meng and J. Garcia-Luna-Aceves, “Channel access using opportunistic
reservations in ad hoc networks,” Mobile Adhoc and Sensor Systems
(MASS), 2006 IEEE International Conference on, pp. 71–80, Oct. 2006.

[8]

S. Merlin, N. Vaidya, and M. Zorzi, “Resource allocation in multi-radio
multi-channel multi-hop wireless networks,” INFOCOM 2008. The 27th
Conference on Computer Communications. IEEE, pp. 610–618, April 2008.

[9]

M. Shin, S. Lee, and Y. ah Kim, “Distributed channel assignment for
multi-radio wireless networks,” Mobile Adhoc and Sensor Systems
(MASS), 2006 IEEE International Conference on, pp. 417–426, Oct. 2006.

[10]

C. Toham, F. Jan, and A. Duda, “Olsr enhancement for multi-interface
multi-channel ad hoc networks,” Mobile Ad Hoc and Sensor Systems,
2008. MASS 2008. 5th IEEE International Conference on, pp. 672–677, 29
2008-Oct. 2 2008.

[11]

H. Wu, F. Yang, K. Tan, J. Chen, Q. Zhang, and Z. Zhang, “Distributed channel
assignment and routing in multiradio multichannel multihop wireless
networks,” Selected Areas in Communications, IEEE Journal on,
vol. 24, no. 11, pp. 1972–1983, Nov. 2006.

[12]

B. P. Zeigler and S. Vahie, “DEVS formalism and methodology: unity of
conception/diversity of application,” in WSC ’93: Proceedings of the
25th conference on Winter simulation.1em plus 0.5em minus 0.4emNew York, NY, USA: ACM Press, 1993, pp. 573–579.

1

Here we define a channel as any
resource, such as a specific frequency or a timeslot, that can be
allocated to nodes in the network

This document was translated from L^AT_EX by
H^EV^EA.