Monday, July 30, 2018

Mengestimasi lokasi node pada Wireless Sensor Network berbasis Raspberry Pi dengan Algoritma Particle Filtering

WSN

Wireless Sensor Network (WSN) merupakan sekumpulan sensor yang saling terhubung secara nirkabel. WSN merupakan salah satu implementasi dari Wireless Ad Hoc Network. (Jaringan) Ad hoc sendiri merupakan jaringan yang dibuat "untuk tujuan khusus" dengan memanfaatkan fasilitas yang ada pada node itu sendiri. Contoh jaringan ad hoc adalah ketika menghubungkan dua laptop atau lebih dengan wifi internal dari salah satu laptop, bukan melalui router. Selain WSN, ada bentuk jaringan ad hoc yang lain seperti: Mobile Ad Hoc networks (MANET), Wireless Mesh Networks (WMN), dan Vehicular Ad Hoc Networks. Silahkan cari sendiri jika ingin tahu lebih detil tentang hal tersebut

Posisi node raspi. Idealnya antar node bisa dikondisikan pada jarak >= 1 m, terletak pada tinggi yang sama dan tidak ada rintangan antar node (pada gambar di atas dock bisa menjadi penghalang/barrier sinyal wifi antar node)

Membuat Jaringan Ad Hoc (dengan Ubuntu dan Raspi)

Untuk membuat jaringan Ad Hoc dengan beberapa Rasperry Pi, kita bisa menggunakan Laptop dengan OS Ubuntu (disini saya memakai Ubuntu 16.04). Langkah-langkah membuat jaringan ad-hoc dengan Ubuntu adalah sebagai berikut:
Setting jaringan ad-hoc pada Ubuntu 16.04
  1. Pada panel jaringan/wifi (gambar panah naik turun), klik "Create new network"
  2. Tulis nama jaringan ad hoc, contoh milik saya: bta-mbp-adhoc
  3. Isikan password jika perlu, kosongi jika ingin menyambungkan raspi dengan jaringan ad hoc tanpa password.
  4. Klik lagi top panel jaringan/wifi, pilih "edit connection"
  5. Pada tab "wifi" pastikan memilih "ad-hoc"
  6. Pada tab "IPV4 Setting", isikan IP address, misal 10.42.0.1, pada net mask isikan "255.255.255.0"
Selesai, cukup mudah. Catatan: Langkah selanjutnya diasumsikan bahwa Raspi telah konek dengan internet dan menginstall paket serta konfigurasi yang dibutuhkan (lihat halaman 1-9 slide INI).

Setelah login melalui ssh (atau bisa juga dengan mengeditnya melalui micro SD), kita perlu menyetting Raspi sebagai berikut.

Edit file /etc/network/interface:
sudo nano /etc/network/interfaces 

Tambahkan file berikut,
auto wlan0
iface wlan0 inet static
    address 10.42.0.3
    netmask 255.255.255.0 
    mtu 1500
    wireless-channel 13 
    wireless-essid bta-mbp-adhoc
    wireless-mode ad-hoc
    wireless-ap any

Ganti IP address dengan IP address yang tadi dimasukkan saat membuat jaringan Ad Hoc di Ubuntu, contohnya tadi saya memasukkan IP 10.42.0.1, maka pada raspi pertama di atas saya masukkan (misal) 10.42.0.3, pada raspi kedua 10.42.0.5, raspi ketiga 10.42.0.7 dan raspi keempat 10.42.0.9. Anda bisa memasukkan IP lain selama tidak bertubrukan, namun akan lebih mudah untuk memberi IP berurutan dan konsisten. Setelah itu restart semua raspi, dan coba konek dengan ssh dengan IP yang diberikan.

Jika anda ingin sharing internet dari PC Ubuntu ke raspi, anda bisa mengikuti tutorial di link ini.

Algoritma Particle Filtering

Skenario yang diberikan adalah sebagai berikut: Ada empat buat raspi dengan posisi, node1(1,1), node2(1,2), node3(2,2), dan node4(2,1). Posisi-posisi tersebut adalah dalam bidang (x,y). Tujuan kita adalah: mengestimasi lokasi dari node1 berdasarkan sinyal wifi yang diterima oleh node1 dari node2, node1 dari no3 dan node1 dari node4.

Untuk memahami algoritma particle filtering, idealnya kita harus ngelontok dulu Kalman Filter dan Monte Carlo sampling. Jika tidak, jangan takut, tetaplah belajar di tautan tersebut (Kalman Filter).  Langkah pertama adalah mengkonfigurasi letak keempat raspberry pi seperti gambar 1 diatas, koordinatnya seperti yang telah dijelaskan pada paragraf sebelumnya. Kemudian, ssh ke keempat raspberry pi tersebut.
ssh -x 10.42.0.3 -l pi
ssh 10.42.0.5 -l pi
ssh 10.42.0.7 -l pi
ssh 10.42.0.9 -l pi
Tampilan di terminal saya adalah seperti di bawah ini.

Pada node1, saya tambahkan argument `-x` karena disitu saya akan membuat plot dengan bantuan matplotlib. Agar tidak terjadi error saat saya menyimpan grafik, maka saya beritahu ssh untuk memforward X11 (display/GUI Linux). Defaultnya, ssh berjalan secara headless, text only.

Beralih ke kode python, bagian pertama program adalah mengimport module, dan mendefinisikan lokasi tiap node sebagai berikut.
import subprocess
import numpy as np
import scipy.stats
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import operator

node1_mac = 'b8:27:eb:48:ec:17'
node2_mac = 'b8:27:eb:12:55:da'
node3_mac = 'b8:27:eb:f1:36:38'
node4_mac = 'b8:27:eb:f3:5b:97'
landmarks_mac = [node1_mac, node3_mac, node4_mac]
landmarks = np.array([[1, 1], [2, 2], [2, 1]])
node_groundtruth = [1, 2]

Fungsi pertama yang akan kita pakai adalah untuk memperoleh nilai RSSI (received signal strength indicator). Oya, sebelum mengonekkan semua node, ada baiknya kita coba secara manual untuk mendapatkan nilai RSSI dengan
iw dev wlan0 station get  
Jika perintah tersebut menghasilkan nilai signal, maka bisa kita lanjutkan dengan fungsi di bawah ini untuk mengekstrak numerik dari sinyal RSSI tersebut.

def get_landmark_rssi(iters):
    print('Begin get landmark rssi...')
    landmark_rssi = []

    for node in landmarks_mac:
        rssi_value = []

        for _ in range(iters):
            command = 'iw dev wlan0 station get ' + node + ' | egrep "signal:"'
            proc = subprocess.check_output(command, shell=True)
            buffer = proc.split(' ')

            RSSI = buffer[2]
            RSSI = RSSI[2:]
            rssi_value.append(int(RSSI))

        landmark_rssi.append(sum(rssi_value) / float(iters))

    return landmark_rssi

Langkah selanjutnya adalah membuat random particle seperti kode berikut,
def create_uniform_particles(x_range, y_range, N, landmarks):
    print('Begin create uniform particles...')
    particles = np.empty((N, 3))
    particles[:, 0] = np.random.uniform(x_range[0], x_range[1], size=N)
    particles[:, 1] = np.random.uniform(y_range[0], y_range[1], size=N)

    for i in range(N):
        landmark_rssi = get_landmark_rssi(5)
        particles[i, 2] = landmark_rssi[0]

    return particles

Kemudian, dari posisi awal random particle tersebut, kita update berdasarkan nilai RSSI yang diperoleh dari node-node lainnya.

def update_particles(particles, weights, z, R, landmarks):
    print('Begin update particles...')
    N = len(particles)

    for j, landmark in enumerate(landmarks):
        distance = np.linalg.norm(particles[:, 0:2] - landmark, axis=1)
        weights *= scipy.stats.norm(distance, R).pdf(z[j])

    weights += 1.e-300
    weights /= sum(weights)

Fungsi lain yang diperlukan adalah fungsi untuk mengestimasi lokasi dari target source (node1). Kita buat fungsi "estimate" berdasarkan mean dan best particle seperti berikut.
def estimate(particles, weights):
    print('Begin estimate...')
    position = particles[:, 0:2]
    mean = np.average(position, weights=weights, axis=0)
    index, value = max(enumerate(weights), key=operator.itemgetter(1))
    best = particles[index, :]
    var = np.average((position - mean) ** 2, weights=weights, axis=0)
    return np.array([[mean[0], mean[1]], [var[0], var[1]], [best[0], best[1]]])

Selanjutnya kita buat fungsi resample. Resample digunakan untuk mengganti sample yang "jauh" dengan sample yang dengan dengan target node. Dengan cara ini, kita akan semaakin dekat dan mendekati target source (node1). Ada tiga fungsi resample yang dibuat: resample (simple), systematic resample dan resample from Index. Hanya dengan menggunakan fungsi resample saja, kita sebenarnya sudah bisa mengganti sample yang jauh dengan sample yang dekat dengan target. Namun dengan kedua fungsi resample lain tadi akan membuat proses estimasi lokasi lebih teliti.
def resample(particles, weights):
    print('Begin resample...')
    N = len(particles)
    cumulative_sum = np.cumsum(weights)
    cumulative_sum[-1] = 1.
    indexes = np.searchsorted(cumulative_sum, np.random.rand(N))

    particles[:] = particles[indexes]
    weights.fill(1.0 / N)

def systematic_resample(weights):
    N = len(weights)

    # make N subdivisions, choose positions 
    # with a consistent random offset
    positions = (np.arange(N) + random()) / N

    indexes = np.zeros(N, 'i')
    cumulative_sum = np.cumsum(weights)
    i, j = 0, 0
    while i < N:
        if positions[i] < cumulative_sum[j]:
            indexes[i] = j
            i += 1
        else:
            j += 1
    return indexes

def resample_from_index(particles, weights, indexes):
    particles[:] = particles[indexes]
    weights[:] = weights[indexes]
    weights.fill (1.0 / len(weights))
Hal lain yang bisa dilakukan adalah dengan membuat fungsi yang mana fungsi tersebut bisa membuat jumlah partikel menjadi lebih efektif. Jadi alih-alih menggunakan semua partikel (misal 10000 partikel), kita hanya akan memakai partikel yang berkontribusi pada distribusi probabilitas dari target. Formula yang digunakan adalah sebagai berikut:
$$ \hat{N}_{eff} = \dfrac{1}{\Sigma w^2} $$
Dalam python, rumus tersebut diimplementasikan seperti di bawah ini.
def neff(weights):
    return 1. / np.sum(np.square(weights))
Sekarang fungsi-fungsi di atas kita panggil dalam sebuah fungi utama yang kita namakan "run_particle_filter" di bawah ini.
def run_particle_filter(N, iters, sensor_std_err, do_plot, plot_particles, xlim, ylim):
    print('Begin run particle filter...')
    #plt.figure()

    particles = create_uniform_particles(xlim, ylim, N, landmarks)

    weights = np.zeros(N)
    weights.fill(1.0 / N)

    for x in range(iters):
        print('Loop ' + str(x + 1) + ' of ' + str(iters))

        rssi_measurement_iteration = 5
        rssi_current = get_landmark_rssi(rssi_measurement_iteration)
        print('RSSI Measurement from each node')
        print(rssi_current)

        update_particles(particles, weights, z=rssi_current, R=sensor_std_err, landmarks=landmarks)

        if neff(weights) < N / 2:
            indexes = systematic_resample(weights)
            resample_from_index(particles, weights, indexes)

        estimation_result = estimate(particles, weights)

#        resample(particles, weights)

        print('Estimate node location')
        print('Mean location:', estimation_result[0])
        print('Best location:', estimation_result[2])
        print(estimation_result)
        print('---------------------------------------------------')

        if plot_particles:
            plt.scatter(particles[:, 0], particles[:, 1], color='k', marker=',', s=1)

        p0 = plt.scatter(node_groundtruth[0], node_groundtruth[1], marker='*', color='k', s=180, lw=3)
        p1 = plt.scatter(landmarks[:, 0], landmarks[:, 1], marker='+', color='k', s=180, lw=3)
        p2 = plt.scatter(estimation_result[:, 0], estimation_result[:, 1], marker='s', color='r')
        plt.xlim(*xlim)
        plt.ylim(*ylim)
        plt.legend([p0, p1, p2], ['target', 'landmarks', 'PF'], loc=4, numpoints=1)
        plt.pause(0.5)
        plt.clf()

    print('Final estimate node location')
    # print(estimation_result)
    print('Mean location:', estimation_result[0])
    print('Best location:', estimation_result[2])
    print('Real node location')
    print(node_groundtruth)
    print('Position error (m)')
    print(np.sqrt(np.square(estimation_result[2][0] - node_groundtruth[0]) + np.square(
        estimation_result[2][1] - node_groundtruth[1])))

    plt.scatter(estimation_result[2][0], estimation_result[2][1], marker='s', color='r')
    plt.scatter(landmarks[:, 0], landmarks[:, 1], marker='+', color='k', s=180, lw=3)
    plt.scatter(node_groundtruth[0], node_groundtruth[1], marker='*', color='k', s=180, lw=3)
    plt.legend([p0, p1, p2], ['target', 'nodes', 'PF_estimate'], loc=4, numpoints=1)
    plt.xlim(*xlim)
    plt.ylim(*ylim)
    #plt.show()
    plt.savefig("find_particle.png")
Dan fungsi utama di atas kita panggil lagi dengan memasukkan variabel-variabel yang dibutuhkan.
run_particle_filter(N=100, iters=20, sensor_std_err=0.1, do_plot=False, plot_particles=False,
                    xlim=(0, 3), ylim=(0, 3))
Jadilah program particle filter untuk mencari lokasi target dari sebuah node WSN. Meski errornya cukup besar (0.2~ m), namun algoritma tersebut telah berjalan dengan baik. Tinggal bagaimana caranya untuk meningkatkan akurasinya. Hasil yang saya peroleh kurang lebih seperti ini.
Kode lengkap dari fungsi-fungsi python di atas dapat diperoleh disini (Code >> find_source.py).
Related Posts Plugin for WordPress, Blogger...