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>