Генерация равномерно распределенных случайных чисел в распределенной среде

Question

Я должен генерировать "уникальное случайное число" в беспроводной сенсорной сети, которая работает по принципу сплетен.

Требования следующие:

1. Каждый узел должен генерировать уникальное случайное число, не имея общих знаний о том, что сгенерировали другие узлы.
2. Распределение сгенерированного случайного числа должно быть равномерным по отношению друг к другу.
3. Было бы предпочтительно, если диапазон генерируемого случайного числа составляет около 10-16 бит или может быть меньше.

Ограничения:

1. Один узел не знает, какое число генерируют другие узлы в сети.
2. Реализация на C, C++.

У меня также есть возможность использовать уникальное начальное число для генерации случайных чисел. семя может быть любым числом в диапазоне 0-2 ^ 15.

Если нет способа генерирования таких чисел, было бы полезно, если бы существовал какой-либо метод, с помощью которого я мог бы удовлетворить некоторые из вышеуказанных требований.

Если бы вы могли предложить мне какой-то способ достичь этого результата, это было бы очень полезно.

Answer 1

Чтобы это решение работало, вы должны знать общее количество узлов в сети генерации. пусть это число будет n,

Основная идея состоит в том, чтобы генерировать равномерно распределенные случайные числа на каждом участвующем узле в течение заданного интервала. n интервалы участвующих узлов не должны перекрываться. общее начальное число не усложняет ситуацию, если общее количество узлов не изменяется, и каждому узлу может быть назначено статически некоторое целое число i <= n так, что каждый номер выдается ровно один раз. вместо того, чтобы генерировать одно случайное число на каждом ходу, n номера генерируются, и узел i принимает iномер из этой серии.

однако общее распределение сгенерированных случайных чисел не будет равномерным, если...:

• Вы синхронизируете генерацию случайных чисел.
• все интервалы имеют одинаковый размер.

информацию о генерации случайных чисел на отдельных узлах смотрите здесь.