騒々しいビープで最適なメッセージ伝達
1Computer Science, Durham University, Durham, DH1 3LE United Kingdom.
まとめ
この研究は,騒々しいビープネットワークでのメッセージ伝送をシミュレートするための最適な手順を導入します. 複雑な分散されたタスクの効率的なシミュレーションの限界を確立し,センサーと生物学的ネットワークのための新しいアルゴリズムを可能にします.
科学分野:
- 分散コンピューティング
- 理論的コンピュータ科学
- ネットワークアルゴリズム
背景:
- ビーピングモデルは,相互作用のために"ビープ" (エネルギーのパルス) のみを使用する単純な通信のネットワークを表します.
- これらのネットワークのノードは,他の情報転送なしで,ビープ (キャリアセンシング) の存在または欠如のみを感知できます.
- 騒々しいビープ音のモデルは ランダムな干渉を導入し コミュニケーションをさらに困難にします
研究 の 目的:
- ビーピングと騒音のビーピングモデルの両方で一般的なメッセージの送信をシミュレートするための最適な手順を開発する.
- 標準的なネットワークプロトコルをシミュレートするために効率的なラウンド複雑性を確立します.
- 複雑な分散グラフアルゴリズムの実装のためのこれらのシミュレーションの適用性を実証する.
主な方法:
- 信号伝送ネットワークにおけるメッセージ伝送シミュレーションのための新しい手順の開発と分析.
- ブロードキャスト CONGEST と CONGEST プロトコルのシミュレーションの上限を,騒音のある/無騒音のビープモデルで導出する.
- 導出されたシミュレーションの複雑さの最適性を示すための下限を証明する.
- 最大マッチングのための既存のブロードキャスト CONGEST アルゴリズムにシミュレーション方法を適用します.
主要な成果:
- ブロードキャスト CONGEST のラウンドは,騒音ビッピングモデルで O ((Δ log n) ラウンドでシミュレートすることができます.
- CONGESTのラウンドは,騒々しいビープのモデルでO ((Δ2 log n) ラウンドでシミュレートすることができます.
- 下限は,これらのシミュレーションの複雑性がアシンプトティックに最適であることを確認します.
- 最大マッチングのためのO(log n) ラウンドのブロードキャストCONGESTアルゴリズムは,騒々しいビープモデルのO(Δ log2 n) ラウンドのアルゴリズムに変換されます.
結論:
- 複雑な分散型タスクは,非常に制限的なノイズビープ通信モデルでも実行可能です.
- 提案されたシミュレーション手順は,標準のネットワークモデルとビープモデルの間の効率的なブリッジを提供します.
- この作業は,最大マッチングなどの高度なグラフアルゴリズムの実装を,リソース制限のあるネットワークで可能にします.
さらに関連する動画
14:05Behavioral Assessment of Hearing in 2 to 4 Year-old Children: A Two-interval, Observer-based Procedure Using Conditioned Play-based Responses
Published on: January 23, 2017
29.2K
10:13A Lightweight, Headphones-based System for Manipulating Auditory Feedback in Songbirds
Published on: November 26, 2012
14.5K
関連する概念動画
Design Example
372
The innovation of touch-tone telephony revolutionized the telecommunications industry by replacing the traditional rotary dial with a dual-tone multi-frequency (DTMF) signaling system. This system uses a matrix-style keypad with buttons arranged in four rows and three columns, creating 12 distinct signals each assigned to a pair of frequencies. Each button press results in a simultaneous generation of two sinusoidal tones – one from a low-frequency group (697 to 941 Hz) and one from a...
372
Amplifying Signals via Second Messengers
7.3K
Many receptor binding ligands are hydrophilic; they do not cross the cell membrane but bind to cell-surface receptors. Thus, their message must be relayed by second messengers present in the cell cytoplasm. There are several second messenger pathways, each with its own way of relaying information. For example, the G protein-coupled receptors can activate both phosphoinositol and cyclic AMP (cAMP) second messenger pathways. The phosphoinositol pathway is active when the receptor induces...
7.3K
Sound Waves: Interference
3.9K
Sound waves can be modeled either as longitudinal waves, wherein the molecules of the medium oscillate around an equilibrium position, or as pressure waves. When two identical waves from the same source superimpose on each other, the combination of two crests or two troughs results in amplitude reinforcement known as constructive interference. If two identical waves, that are initially in phase, become out of phase because of different path lengths, the combination of crests with troughs...
3.9K
Amplifying Signals via Enzymatic Cascade
8.7K
When a ligand binds to a cell-surface receptor, the receptor's intracellular domain changes shape, which may either activate its enzyme function or allow its binding to other molecules. The initial signal is amplified by most signal transduction pathways. This means that a single ligand molecule can activate multiple molecules of a downstream target. Proteins that relay a signal are most commonly phosphorylated at one or more sites, activating or inactivating the protein. Kinases catalyze...
8.7K
Signal Sequences and Sorting Receptors
5.6K
Signal sequences are short amino acid sequences that guide newly synthesized proteins to their proper location within the cell. Classical signal sequences are fifteen to sixty amino acids long and present at the N-terminus of a polypeptide chain. Each signal sequence has a conserved segment of basic residues towards their N terminus, a hydrophobic core, and a C-terminus rich in polar residues. The C-terminus also contains a signal cleavage site and features a -3 -1 sequence motif. The -3-1...
5.6K
Echo
599
The human ear cannot distinguish between two sources of sound if they happen to reach within a specific time interval, typically 0.1 seconds apart. More than this, and they are perceived as separate sources.
Imagine the sound is reflected back to the ears. Assuming that the source is very close to the human, the difference between hearing the two sounds—the emitted sound and the reflected sound—may be more than the minimum time for perceiving distinct sounds. If this is the case,...
Imagine the sound is reflected back to the ears. Assuming that the source is very close to the human, the difference between hearing the two sounds—the emitted sound and the reflected sound—may be more than the minimum time for perceiving distinct sounds. If this is the case,...
599
