Abstract-Vi definierar och studerar schemaläggning komplexiteten i trådlösa nätverk, som uttrycker den teoretiskt uppnåeliga effektiviteten av MAC skikt protokoll. Med tanke på en uppsättning förfrågningar om kommunikation i godtyckliga nätverk, beskriver schemaläggning komplexiteten den tid som krävs för att framgångsrikt schemalägga alla förfrågningar. Den mest grundläggande och viktiga nätverksstrukturen i trådlösa nätverk är konnektivitet, vi studerar schemaläggning komplexiteten i konnektivitet, dvs. den minimala tid som krävs tills en ansluten struktur kan schemaläggas. I detta dokument, vi bevisar att schemaläggning komplexiteten av konnektivitet växer bara polylogaritmiskt i antalet noder. Specifikt presenterar vi en ny schemaläggningsalgoritm som framgångsrikt schemalägger en starkt ansluten uppsättning länkar i tid O(log 4 n) även i godtyckliga värsta-fall-nätverk. Å andra sidan bevisar vi att standard MAC lager eller schemaläggning protokoll kan utföra mycket värre. I synnerhet har alla protokoll som antingen använder en enhetlig eller linjär (en nods sändningseffekt står i proportion till den minsta effekt som krävs för att nå den avsedda mottagaren) krafttilldelningen en (n) schemaläggningskomplex i värsta fall, även för enkla kommunikationsförfrågningar. Däremot tillåter vår polylogaritmiska schemaläggningsalgoritm många samtidiga överföringar genom att använda ett explicit formulerat icke-linjärt krafttilldelningsschema. Våra resultat visar att det inte finns några teoretiska skalbarhetsproblem när det gäller schemaläggning av överföringsförfrågningar även i stora, värsta nät, vilket ger ett intressant komplement till de mer pessimistiska gränserna för kapaciteten i trådlösa nät. Alla resultat baseras på den fysiska kommunikationsmodellen, som tar hänsyn till att signaltonoise plus interferens ratio (SINR) vid en mottagare måste ligga över ett visst tröskelvärde om överföringen ska tas emot korrekt.
I dokumentet Ref studerar schemaläggning komplexiteten i att ansluta ett visst antal noder som ligger på godtyckliga positioner av vissa kommunikationsträd.
The Complexity of Connectivity in Wireless Networks
{'venue': 'Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications', 'journal': 'Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}