Algoritma apa yang harus saya gunakan untuk geolokasi wifi?

16

Kasus Penggunaan Penjemputan Sekolah (pembaruan)

Mungkin bermanfaat untuk menggunakan case penggunaan yang lebih konkrit daripada contoh halaman belakang asli di bawah ini. Penegakan hukum setempat telah mulai menindak penggunaan SMS dan penggunaan ponsel di zona sekolah. Ini menghadirkan masalah bagi orang tua menjemput anak-anak setelah fungsi sekolah menengah. Bahkan bagi mereka yang memamerkan hukum, menara sel dengan cepat menjadi kelebihan ketika ratusan anak memanggil orang tua mereka sekaligus. Kampusnya besar, dengan jangkauan wifi. Sepertinya mungkin untuk menulis aplikasi seluler yang memungkinkan pengguna ponsel mengirim pesan teks berisi daftar kekuatan sinyal wifi ke layanan web. Layanan web kemudian akan membuat perbaikan lokasi dan mendorong pesan ke perangkat navigasi di papan induk. Orang tua kemudian akan pergi ke lokasi yang benar di kampus.

Casing Penggunaan Halaman Belakang (asli) Ketika saya membawa laptop saya ke halaman belakang dan memilih "lihat jaringan yang tersedia", saya melihat daftar 4 tetangga saya. Saat saya berjalan, sinyal relatif menguat dari tetangga saya yang berubah.

Saya ingin berdiri dengan laptop saya di lokasi yang diketahui di halaman belakang saya, klik pada peta dan kumpulkan poin dengan 4 kekuatan sinyal berbeda.

Setelah mengumpulkan banyak (tapi tidak terlalu banyak) dari titik-titik kalibrasi ini, saya ingin kemudian menulis sebuah program yang mengambil 4 tingkat kekuatan sinyal wifi dan memperkirakan lokasi dalam bentuk ellipse kesalahan. Sinyal mungkin diukur menggunakan perangkat yang berbeda dari yang digunakan untuk mengumpulkan titik kalibrasi asli.

Algoritma apa yang harus saya gunakan?

Saya tidak ingin mengganggu tetangga saya dengan menanyakan apakah saya bisa masuk dan mensurvei lokasi persis dari router mereka.

Saya dapat berasumsi, bagaimanapun, lokasi router tetangga saya tidak berubah.

Kirk Kuykendall
sumber
4
saya pikir dia hanya ingin melakukan triangulasi, bukan dukung-dukungan ...
Marinheiro
Tanpa dukungan - hanya kekuatan sinyal, yang sah untuk diukur, bukan? Saya tidak akan menjadi "googling" wifi ... blogs.discovermagazine.com/80beats/2010/10/25/…
Kirk Kuykendall

Jawaban:

6

Kedengarannya Anda tidak tahu lokasi sinyal dengan sangat baik, jadi Anda harus terlebih dahulu memperkirakannya dan kemudian, mengingat perkiraan itu, melakukan pelacakan posisi Anda.

Jika Anda menginginkan akurasi dan realisme, pertimbangkan untuk mengadopsi model kemungkinan untuk kekuatan sinyal, menemukan kemungkinan maksimum, dan membuat peta peluang lokasi yang dikomputasi dari perkiraan kemungkinan maksimum. Global maksimum pada kisi mengidentifikasi perkiraan terbaik dari lokasi dan kontur (relatif terhadap maksimum) memberikan set kepercayaan untuk lokasi itu.

Model kemungkinan umum diperoleh dengan menempatkan formula untuk pelemahan sinyal dan memungkinkan untuk kesalahan. Anda tidak akan terlalu jauh dengan formula yang sepenuhnya umum (dengan fungsi redaman yang bergantung pada sudut dan lokasi), jadi Anda harus menyederhanakannya. Misalnya, Anda dapat mempertimbangkan fungsi pelemahan "universal", sebut saja f , sehingga jika kekuatan sumber di lokasi WiFi x sama dengan a maka kekuatan yang diharapkan di lokasi lain y diberikan oleh

z (y; x) = af (| y - x |).

Sebagai contoh, Anda dapat mempertimbangkan pelemahan kuadrat terbalik yang f (t) = 1 / t ^ 2 asalkan jarak t lebih besar dari beberapa ambang batas kecil. Sebagai penyederhanaan lain, Anda dapat mengambil kekuatan membaca z (y; x) di lokasi y untuk sumber di x berbeda dari nilai yang diharapkan oleh kesalahan yang didistribusikan secara normal; menganggap semua kesalahan independen; dan menganggap mereka semua memiliki deviasi standar yang sama ( s ). Kontribusi pada log kemungkinan pembacaan kekuatan z kemudian menjadi

L (y, x) = - [(z (y; x) - af (| yx |) ^ 2 / s ^ 2 + ln (s)] / 2.

Kemungkinan log untuk dimaksimalkan adalah jumlah ganda L (y, x) di atas semua lokasi y dan semua sumber x . Ini adalah fungsi dari lokasi yang tidak diketahui, intensitas sumber tidak diketahui, dan standar deviasi kesalahan yang tidak diketahui. Sangat mudah untuk menemukan standar deviasi optimal dan intensitas sumber optimal (ambil turunan parsial, atur nilainya menjadi nol, dan pecahkan), tetapi untuk fungsi atenuasi realistis jika Anda memiliki masalah non-linear untuk menemukan lokasi. Namun, dalam contoh Anda ini hanya melibatkan 13 parameter sehingga Anda harus dapat memasukkannya ke dalam, katakanlah, pengoptimal multivarian Newton-Raphson dan dengan cepat mendapatkan jawaban yang baik. (Literatur statistik penuh dengan metode untuk menyelesaikan persamaan semacam ini.)

Jika Anda juga menganggap perangkat kedua memiliki sensitivitas yang lebih besar secara proporsional daripada perangkat pengumpulan data, itu akan membuat sedikit perbedaan dalam model yang saya usulkan (karena kekuatan sinyal masuk secara berlipat ganda). Bahkan, jika Anda membiarkan kesalahan skala dengan intensitas (sehingga mereka memiliki standar deviasi a * s * daripada s ) perbedaan antara perangkat harus tidak penting.

Untuk menjaga ini tetap sederhana, saya telah melewatkan beberapa statistik statistik, seperti fakta bahwa ini adalah masalah interval prediksi multivariat, bukan masalah interval kepercayaan. Jika jumlah kesalahan tidak besar (yaitu, s kecil), perbedaannya tidak akan banyak konsekuensi.

whuber
sumber
Terima kasih Bill, ini terlihat bisa dilakukan. Dengan laptop saya baru menyadari sinyal sensitif terhadap orientasi antena. Tidak yakin apakah ini benar dengan ponsel. Apakah perbaikan lokasi cukup baik untuk kasus penggunaan sekolah menengah?
Kirk Kuykendall
Anda dapat menangani orientasi tetapi menjadi lebih rumit dan akan membutuhkan lebih banyak bacaan. Sebaiknya gunakan sinyal maksimum di antara semua orientasi yang dimungkinkan di setiap titik. Kasus penggunaan sekolah menengah adalah varian yang menarik karena disarankan melakukan yang terbaik untuk mengidentifikasi lokasi dan kekuatan pengirim WiFi sekali dan untuk semua. Setelah itu latihan triangulasi. Satu kekhawatiran yang saya miliki adalah bahwa kekuatan sumber dapat bervariasi, seringkali tidak dapat diprediksi. Itu benar-benar dapat mengacaukan triangulasi. Pertimbangkan untuk menambahkan layar awal untuk sinyal yang lebih rendah (rendah) sehingga tidak merusak perbaikannya.
whuber
0

Jika Anda mengumpulkan lokasi dengan gps saya pikir Anda melihat dua faktor kesalahan yang berbeda. satu untuk gps dan yang lainnya untuk kekuatan sinyal.

Brad Nesom
sumber
Dalam konteks ini, Kirk benar-benar dapat memverifikasi lokasi di halaman belakangnya secara mandiri (yaitu hanya mengambil beberapa pembacaan GPS dari setiap lokasi).
Andy W
0

Tidak bisakah Anda memanfaatkan salah satu sistem pemosisian WiFi yang ada seperti Skyhook Wireless atau Core Location di iOS Apple? Skyhook memungkinkan Anda untuk menambahkan alamat MAC Wi-Fi ke database mereka secara manual, iOS mengumpulkan alamat MAC Wi-Fi secara otomatis menggunakan iPhone yang dilengkapi GPS.

Ortwin Gentz
sumber
Ini mungkin bukan ide yang buruk jika dia ingin mencari tahu di mana dia berada. Tapi dia berusaha mencari cara untuk mengumpulkan lokasi jaringan sendiri. Selain itu, ia mencoba melakukan triangulasi posisinya berdasarkan kekuatan sinyal WiFi. Saya tidak yakin apakah solusi komersial melakukan itu.
jvangeld
@ jvangeld: Sejauh yang saya mengerti, Core Location di iOS menggunakan kekuatan sinyal Wi-Fi untuk melakukan pelacakan posisi. Untuk kasus penjemputan sekolah yang disebutkan di atas, itu akan menjadi cara untuk pergi.
Ortwin Gentz
0

Gereja,

Walaupun saya mungkin salah, saya pikir Anda terlalu rumit. Meskipun untuk bersikap adil, tidak berasal dari bagian dunia Anda, saya tidak tahu keterbatasan apa yang Anda hadapi di lingkungan kampus sekolah.

Sementara sebagian besar perangkat seluler sudah mendukung triangulasi GPS dan atau menara seluler, untuk WiFi, SkyHook adalah jawabannya karena alasan berikut: 1. Basis data lokasi WiFi mereka BESAR. 2. Setiap kali aplikasi menggunakan SkyHook digunakan, itu menambah jaringan WiFi yang baru ditemukan ke database, dengan posisi. Jadi semakin banyak digunakan di suatu daerah, semakin akurat jadinya. Saya menduga bahwa di lokasi dengan kepadatan tinggi seperti kampus, jika tidak ada cakupan yang baik, maka akan ada dalam beberapa hari penggunaan reguler. 3. Beberapa telepon menggunakan SkyHook sebagai bagian dari API lokasi mereka, yang berarti bahwa semakin banyak API telepon normal akan sudah terpasang.

Sejujurnya, kecuali jika Anda menginginkan layanan ini tersedia di laptop (sebagian besar browser baru memiliki SkyHook), sebagian besar ponsel sekarang memiliki GPS, yang dapat diakses melalui API telepon asli, baik itu iOS, Android, WP7 atau BlackBerry Opsi lainnya adalah menjadikannya aplikasi web seluler, yang hanya akan menggunakan API lokasi browser, dengan akses ke semua alat lokasi di telepon.

BlinkyBill
sumber
Saya pikir skyhook mengumpulkan data melalui wardriving. Saya tidak bisa membayangkan mereka berkendara ke jalan sekolah, meskipun saya kira itu adalah untuk umum.
Kirk Kuykendall
Anda benar, tetapi karena klien 'memperluas' database mereka sebagai tambahan untuk perang, mereka mungkin akan tetap memiliki cakupan. Anda selalu dapat menguji dengan memuat Opera ke laptop Anda, pergi ke kampus dengan maps.google.com dan WiFi diaktifkan, dan lihat di mana ia menempatkan Anda.
BlinkyBill