ABSTRAK
Komunikasi dengan topologi mesh (selanjutnya disebut matajala) dan multi-hop, saat ini mendapat perhatian luas dari para peneliti, dan diperkirakan menjadi salah satu topologi utama dalam jaringan ubiquitous / pervasive masa depan. Dengan kemampuan self organized, self configured, self healing, topologi jaringan ini memiliki berbagai potensi kelebihan, berupa sifat kokoh, implementasi yang cepat, cakupan layanan yang lebih luas, serta biaya murah karena berkurangnya kebutuhan akan infrastruktur, dibandingkan topologi jaringan tersentralisasi point to point yang mendominasi topologi jaringan akses pada saat ini. Penelitian disertasi ini terkonsentrasi pada optimalisasi algoritma alokasi sumberdaya radio yang merupakan area penelitian yang sangat ekstensif untuk jaringan nirkabel matajala, dengan timeslot adalah sumberdaya radio yang ditinjau. Untuk jaringan matajala nirkabel, protokol dasar time division multiple access (TDMA) dapat dikembangkan menjadi spatial time division multiple access (STDMA), yang memungkinkan alokasi sumberdaya waktu yang sama untuk sejumlah transmisi link/node yang berbeda dan terpisah secara spasial geografis.Penelitian disertasi memiliki tujuan untuk mendapatkan algoritma alokasi timeslot berkompleksitas waktu rendah dengan tetap mempertahankan serta meningkatkan unjuk kerja kapasitas throughput pada jaringan. Kebutuhan akan algoritma berkompleksitas waktu rendah pada dasarnya dimaksudkan untuk memperbaiki respon adaptasi algoritma terhadap mobilitas dan perubahan topologi. Sementara itu, kebutuhan untuk mempertahankan dan meningkatkan kapasitas throughput disebabkan karena jaringan matajala nirkabel adalah jaringan data yang selalu berorientasi pada peningkatan kapasitas jaringan.Pendekatan yang dilakukan untuk memperoleh algoritma dengan kompleksitas waktu yang rendah adalah dengan mengembangkan algoritma aproksimasi berbasis greedy yang dikombinasikan dengan partisi geometris, sehingga proses inspeksi SINR tidak perlu melibatkan keseluruhan link transmisi, yang berakibat pada penurunan kompleksitas waktu. Lalu peningkatan performa kapasitas throughput diperoleh dari penggunaan bobot penjadwalan yang lebih representatif dalam mewakili besaran interferensi dibandingkan interference number yang digunakan dalam algoritma greedy konvensional. Dengan pendekatan ini, algoritma greedy terbobot dengan partisi geometrik yang diusulkan mampu mendekati kinerja algoritma penjadwalan link terbaik pada area penelitian terkait, yaitu algoritma SGLS dengan rasio aproksimasi 92,86% dengan kompleksitas waktu. Usaha penelitian berikutnya dalam peningkatan kapasitas jaringan adalah pengembangan metode baru penjadwalan link berbasis keputusan dengan relaksasi konstrain SINR dalam model interferensi fisik. Metode ini mampu memberikan derajat kebebasan untuk meningkatkan kapasitas jaringan pada tingkat probabilitas cakupan yang dapat ditoleransi. Dari hasil simulasi sebagai contoh, rasio aproksimasi penjadwalan dap at ditingkatkan menuju maksimum dengan kompleksitas waktu dipertahankan tetap, dengan catatan bahwa probabilitas cakupan matajala ditoleransi untuk dikurangi. Pendekatan baru dalam desain algoritma ini sekaligus juga menegaskan adanya keterkaitan antara kapasitas, kualitas, dan cakupan pada jaringan matajala nirkabel yang terkait algoritma penjadwalan link yang didesain. Untuk itu, penelitian ini juga menawarkan parameter metrik baru dalam desain algoritma penjadwalan link pada jaringan matajala nirkabel, yaitu probabilitas cakupan matajala dan marjin SINR disamping pengulangan spasial. Ketiga parameter metrik itu selanjutnya dapat digunakan sebagai parameter perbandingan algoritma yang lebih komprehensif dalam penelitian karakteristik jaringan matajala nirkabel.

---

ABSTRACT
Today, communication with mesh and multihop topology receives wide attention of researchers, and is expected to become one of the main topologies in the ubiquitous and pervasive networks. With the ability to be self organized, self configured, self healing, this network topology has many potential advantages, such as the robustness, fast implementation, broader scope of services, as well as low cost due to the reduced need for infrastructure, compared to a point to point centralized network topology communication that dominates the access network technology at this time.This research is concentrated on the development and optimization of spatial time division multiple access (STDMA) radio resource allocation algorithm, which is a very extensive research area in wireless mesh network area. STDMA is an access protocol that is developed from time division multiple access (TDMA). So, STDMA has advantage to maintain QoS as well as TDMA. STDMA access protocols allow the same time as radio resource allocated to different link or node transmission that are spatially separated geographically, as long as the multiple transmissions in the same timeslot do not mutually interfere.This study has the objective to obtain a low computational complexity resource allocation algorithm while maintaining and improving the performance of network capacity in wireless mesh network. The need of low time complexity radio resource algorithms for wireless mesh network is intended to improve the algorithm response in mobility and topology changes. Meanwhile, there is a need to increase the network capacity since wireless mesh network is a data network. The research proposes the algorithm with low computational complexity by developing an approximation algorithm based on greedy algorithm combined with.geometric partition to limitate the process of SINR calculation. This approach results in a reduction in complexity. To increase network capacity, we propose the use of weight scheduling to represent the interference more accurately than interference number that is used in the conventional greedy algorithm. With those approaches, the modified greedy algorithm with a weighted geometric partitioning proposed scheduling algorithm is able to achieve the network capacity near to the best result in this area of research, i.e SGLS algorithm, with the approximation ratio of 92.86% in a lower time complexity.The next research effort is the development of the new approach to design link scheduling decision based on relaxation of SINR constraint. This method provides a degree of freedom to increase wireless mesh network capacity in the certain tolerated mesh coverage probability. From the simulation results as examples, this method can improve the appr oximation ratio of scheduling up to maximum with a sustained time complexity remains, with the mesh coverage probability is tolerated to be reduced.The new approach in the design of link scheduling algorithm at the same time also confirms the relationships among capacity, quality, and coverage on the wireless mesh network that is related to the designed link scheduling algorithm. Therefore, this study also offers new metric parameters in the design of the mesh link scheduling algorithm, i.e. the mesh coverage probability, and SINR margin in addition to the spatial reuse as a common previous metric. The three metric parameters can then be used as the algorithm's benchmark parameters for comprehensive wireless mesh network characterization research.