Quick summary: it might work but I haven't figured out how to make it
work.
<html><head><title>Random bit-vector network addressing</title>
<!-- see end of file for explanation, where it's put so that it's readable in
the browser -->
<script src="../MochiKit-1.3.1/lib/MochiKit/MochiKit.js"></script>
<script type="text/javascript">
var bits_per_cell, bits_per_row, cells_per_row, cells_per_col, table
var randbits = []
function replenish_bits() {
var num = Math.random()
for (;;) {
num *= 2
if (num > 1) {
randbits.push(1)
num -= 1
} else if (num == 1) {
if (randbits.length) return
else num = Math.random()
} else {
randbits.push(0)
}
}
}
function random_bit() {
if (!randbits.length) replenish_bits()
return randbits.pop()
}
function random_bitvector(length) {
return map(random_bit, range(length)).join('')
}
function how_many_bits_per_row(total_bits) {
/* make roughly square */
var max = Math.ceil(Math.sqrt(bits_per_cell * 4))
var min = Math.ceil(max/2)
var ii = max
for (var ii = max; ; ii--) {
if (ii == min || total_bits % ii == 0) return ii
}
}
function reset() {
bits_per_cell = $('bits_per_cell').value
cells_per_row = $('cells_per_row').value
cells_per_col = $('cells_per_col').value
bits_per_row = how_many_bits_per_row(bits_per_cell)
table = map(function() {
return map(function() {
return random_bitvector(bits_per_cell)
}, range(cells_per_row))
}, range(cells_per_col))
refresh()
}
function display_cell(cellvalue) {
var rv = []
while (cellvalue.length) {
rv.push(cellvalue.substr(0, bits_per_row))
rv.push(BR())
cellvalue = cellvalue.substr(bits_per_row)
}
return rv
}
function refresh() {
replaceChildNodes('dest', TABLE({cellPadding: 2, cellSpacing: 0},
map(function(ii) {
return TR(null, map(function(jj) {
var tcc = function(ev) { turn_cells_colors(ii, jj) }
var rv = TD(null, display_cell(table[ii][jj]))
connect(rv, 'onclick', tcc)
return rv
}, range(table[0].length)))
}, range(table.length))))
}
function similarity(r0, c0, r1, c1) {
var b0 = table[r0][c0]
var b1 = table[r1][c1]
var count = 0
forEach(range(b0.length), function(ii) {
if (b0[ii] == b1[ii]) count++
})
return count / b0.length
}
function similarity_color(r0, c0, r1, c1) {
var sim = similarity(r0, c0, r1, c1)
if (sim == 1) return '#77ff77'
/* Map similarities of one-third and up into colors ranging from
* white, through pink, into red. Bizarrely fromHSV(1, 0, 1) is black,
* though fromHSV(1, 0.001, 1) or fromHSV(1, -0.001, 1) are white */
return Color.fromHSV(1, 1.5*sim - 0.499, 1).toHexString()
}
function turn_cells_colors(r0, c0) {
set_cell_backgrounds(function(ii, jj) {
return similarity_color(r0, c0, ii, jj)
})
}
function colors_by_bit(n) {
set_cell_backgrounds(function(ii, jj) {
return table[ii][jj][n] == '1' ? 'white' : 'gray'
})
}
function set_cell_backgrounds(cell_color_func) {
var domtable = $('dest').firstChild
var ii = 0
var jj = 0
function turn_a_cell() {
domtable.childNodes[ii].childNodes[jj].style.background =
cell_color_func(ii, jj)
jj++
if (jj == table[0].length) {
ii++
jj = 0
}
if (ii < table.length) setTimeout(turn_a_cell, 0)
}
turn_a_cell()
}
function neighbors(ii, jj) {
function in_bounds(arg) {
var ii = arg[0], jj = arg[1]
return ii >= 0 && jj >= 0 && ii < table.length && jj < table[0].length
}
function get_cell(arg) { return table[arg[0]][arg[1]] }
return map(get_cell, filter(in_bounds,
[[ii, jj], [ii-1, jj], [ii, jj-1],
[ii+1, jj], [ii, jj+1]]))
}
function majority_rule_digit(digits) {
var counts = [0, 0]
forEach(digits, function(digit) { counts[digit] += 1 })
if (counts[0] > counts[1]) return 0
else if (counts[1] > counts[0]) return 1
else return random_bit()
}
function random_rule_digit(digits) {
var counts = [0, 0]
forEach(digits, function(digit) { counts[digit]++ })
return (Math.random() < counts[0] / (counts[0] + counts[1])) ? 0 : 1
}
function map_digits(digit_rule, neighbors) {
var rv = map(digit_rule, map(function(ii) {
return map(function(neighbor) { return neighbor[ii] },
neighbors)
}, range(neighbors[0].length)))
return rv.join('')
}
current_digit_rule = random_rule_digit
function change_rule(select_object) {
var o = select_object.options[select_object.selectedIndex].value
if (o == 'majority_rule_digit') current_digit_rule = majority_rule_digit
else current_digit_rule = random_rule_digit
}
function mix_cell(ii, jj) {
return map_digits(current_digit_rule, neighbors(ii, jj))
}
function propagate(continuation) {
var newtable = []
var ii = 0
var jj = 0
var newrow = []
/* explicit CPS loop to avoid "script has stopped responding" message */
function do_cell() {
newrow.push(mix_cell(ii, jj))
jj++
if (jj == table[0].length) {
jj = 0
newtable.push(newrow)
newrow = []
ii++
}
if (ii < table.length) setTimeout(do_cell, 0)
else {
table = newtable
refresh()
if (continuation) continuation()
}
}
do_cell()
}
function propagate_n(n) {
if (n > 0) propagate(function(){propagate_n(n-1)})
}
function init() {
reset()
}
</script>
</head>
<body onload="init()">
<h1>Random bit-vector network addressing</h1>
<p style="font-size: 2em">
<button onclick="propagate_n($('n').value)">propagate</button> <input id="n"
value="1" size="3"> times using a
<select onchange="change_rule(this)" id='current_digit_rule'>
<option selected="selected"
value="random_rule_digit">stochastic</option>
<option value="majority_rule_digit">mostly deterministic</option>
</select> rule, click on a cell to color other cells by similarity,
<button onclick="colors_by_bit($('bit').value)">color</button> by bit
<input id="bit" value="0" size="3" /> (
<button onclick="$('bit').value++; colors_by_bit($('bit').value)"
>up</button>,
<button onclick="$('bit').value--; colors_by_bit($('bit').value)"
>down</button>),
or <button onclick="reset()">reset</button> with
<input id="cells_per_col" value="15" size="3"> rows of
<input id="cells_per_row" value="15" size="3"> cells containing
<input id="bits_per_cell" value="32" size="4"> bits each.
</p>
<div id="dest"></div>
<h2>Explanation</h2>
<p>So I had this very simple idea for doing geographical addressing
and routing in ad-hoc mesh networks. Every node starts by generating
a random ID, and then for some number of generations, executes the
following procedure:</p>
<ol>
<li>Send all your neighbors your current ID.</li>
<li>Receive all your neighbors' IDs.</li>
<li>Given your own ID and your neighbors' IDs, calculate a new ID for
yourself that is somehow more similar to your neighbors' IDs than your
old ID was.</li>
</ol>
<p>The idea is that, after some number of generations, much of the
local variation will be smoothed out of the ID space, so that you can
route a message to a node by forwarding it to whichever one of your
neighbors has the ID most similar to the destination node's ID, or
possibly choose one of your neighbors at random weighted by that
function.</p>
<p>There's a bit of tension in this idea --- if the smoothing process
is totally effective, every node will end up with the same ID, making
them useless for addressing, and if it's not that effective but still
rather too effective, there won't be much local variation in ID, so it
will be hard to figure out which direction a message should go in.
But if it's not smooth enough, the message won't make progress towards
its destination.</p>
<p>So this is a little experiment to try this idea out. Each node has
a 32-bit randomly-generated address to start out; it's topologically
connected to the cells above and below it and to its left and right;
"similarity" is Hamming distance, new IDs are calculated bit by bit,
and there are two algorithms available for making an ID bit "more
similar" to those of a node's neighbors':</p>
<dl>
<dt>stochastic</dt>
<dd>The node's and neighbors' 0 bits (in a particular position,
e.g. bit #11) are counted; the new bit is 0 with probability N/M,
where N is the number of 0 bits found, and M is the total number of
bits (5 for most nodes, ranging down to 3 in the corners). So if all
the bits examined are the same, the new bit is guaranteed to have the
same value; but if e.g. a single bit out of 5 is 0, then the new bit
is 0 with 20% probability and 1 with 80% probability.</dd>
<dt>mostly deterministic</dt>
<dd>The same set of bits are examined, but the new bit is the value
taken by the majority of the old bits (or uniformly randomly selected
if there was a tie, which can happen at the edges)</dd>
</dl>
<h2>Results</h2>
<p>It doesn't work as well as I would like. Neither of the algorithms
is very effective at eliminating "local optima" on 32-bit IDs in a
15x15 grid, even after a large number of generations. The
mostly-deterministic algorithm does eliminate the majority of local
bumpiness in the closeness function, so messages started nearby would
propagate successfully.</p>
<p>Neither algorithm is "effective" enough to produce noticeable
numbers of identical IDs.</p>
<p>Unsurprisingly, both algorithms seem to work if the number of bits
is larger than the number of nodes, as long as you run them long
enough. But maybe that's just because I haven't been able to wait
very long to run largish simulations with a lot of bits.</p>
<p>The deterministic algorithm seems to mostly settle down after a few
generations, maybe 10 or 20, which means that no new information is
being transmitted at that point. This is bad news, since in 10 or 20
generations, information can only flow (optimistically) 10 or 20 hops.
It gets a little bit better with more bits, but not a lot.</p>
<h2>Other directions</h2>
<p>It might be possible to rescue this approach in one or more of the
following ways:</p>
<ul>
<li>Randomly flip bits from time to time as a modification to the
mostly-deterministic algorithm.</li>
<li>Rather than using vectors of individual bits, use vectors of small
integers, perhaps of 2 or 3 bits each; then "more similar" IDs might
be a median, or stochastically chosen from near the median.</li>
<li>Change some bits more slowly than others, or change some bits
according to the stochastic algorithm, and the others according to the
majority-rule algorithm.</li>
<li>Gradually "anneal" the IDs: start with the stochastic algorithm
(or an algorithm where the bits are just uniformly selected each
step), then gradually increase the probability weight from the local
majority.</li>
</ul>
</body>
</html>
