Question
I have tried to implement leader election algorithm on a ring(made up of nodes) in c programming on Kilombo in linux. However, I am facing
I have tried to implement leader election algorithm on a ring(made up of nodes) in c programming on Kilombo in linux. However, I am facing an issue with the code. The code is taking more time for electing the leader, also when the leader node is removed, the remaining ring does not elect leader again among themselves. I am posting the c file and h file below.
Can you please go through the code and help me correct the code for the problem mentioned above.
*************************************************************************************************************************************************************************
"le.c"
#define SIMULATOR
#ifndef SIMULATOR
#include
#include
#include "le.h"
USERDATA myData;
USERDATA *mydata = &myData;
#else
#include
#include
#include
#include "le.h"
REGISTER_USERDATA(USERDATA)
#endif
int resetLeft = 0;
int resetRight = 0;
char isQueueFull()
{
return (mydata->tail +1) % QUEUE == mydata->head;
}
/* Helper function for setting motor speed smoothly
*/
void smooth_set_motors(uint8_t ccw, uint8_t cw)
{
// OCR2A = ccw; OCR2B = cw;
#ifdef KILOBOT
uint8_t l = 0, r = 0;
if (ccw && !OCR2A) // we want left motor on, and it's off
l = 0xff;
if (cw && !OCR2B) // we want right motor on, and it's off
r = 0xff;
if (l || r) // at least one motor needs spin-up
{
set_motors(l, r);
delay(15);
}
#endif
// spin-up is done, now we set the real value
set_motors(ccw, cw);
}
void set_motion(motion_t new_motion)
{
switch(new_motion) {
case STOP:
smooth_set_motors(0,0);
break;
case FORWARD:
smooth_set_motors(kilo_straight_left, kilo_straight_right);
break;
case LEFT:
smooth_set_motors(kilo_turn_left, 0);
break;
case RIGHT:
smooth_set_motors(0, kilo_turn_right);
break;
}
}
char in_interval(uint8_t distance)
{
//if (distance >= 40 && distance <= 60)
if (distance <= 90)
return 1;
return 0;
}
//
char is_stabilized()
{
uint8_t i=0,j=0;
for (i=0; i
{
if ((mydata->nearest_neighbors[i].state == AUTONOMOUS && mydata->nearest_neighbors[i].num > 2) ||
(mydata->nearest_neighbors[i].state == COOPERATIVE && mydata->nearest_neighbors[i].num_cooperative > 2))
j++;
}
return j == mydata->num_neighbors;
}
// Search for id in the neighboring nodes
uint8_t exists_nearest_neighbor(uint8_t id)
{
uint8_t i;
for (i=0; i
{
if (mydata->nearest_neighbors[i].id == id)
return i;
}
return i;
}
// Search for id in the neighboring nodes
uint8_t are_all_cooperative()
{
uint8_t i;
for (i=0; i
{
if (mydata->nearest_neighbors[i].state == COOPERATIVE)
return 0;
}
return 1;
}
uint8_t get_nearest_two_neighbors()
{
uint8_t i, l, k;
uint16_t min_sum = 0xFFFF;
k = i = mydata->num_neighbors;
if (are_all_cooperative())
{
for (i=0; i
{
// shortest
if (mydata->nearest_neighbors[i].distance < min_sum)
{
k = i;
}
}
if (k < mydata->num_neighbors)
{
i = k;
}
}
else
{
for (i=0; i
{
// Is it cooperative and at distance in [4cm,6cm]?
if (mydata->nearest_neighbors[i].state == COOPERATIVE)
{
l = exists_nearest_neighbor(mydata->nearest_neighbors[i].right_id);
// Does the right exits in my table?
if (l < mydata->num_neighbors)
{
if (mydata->nearest_neighbors[i].distance +
mydata->nearest_neighbors[l].distance < min_sum)
{
min_sum = mydata->nearest_neighbors[i].distance + mydata->nearest_neighbors[l].distance;
k = i;
}
}
}
}
if (k < mydata->num_neighbors)
{
i = k;
}
}
return i;
}
char enqueue_message(uint8_t m)
{
#ifdef SIMULATOR
//printf("%d, Prepare %d ", mydata->my_id, m);
#endif
if (!isQueueFull())
{
mydata->message[mydata->tail].data[MSG] = m;
mydata->message[mydata->tail].data[ID] = mydata->my_id;
mydata->message[mydata->tail].data[RIGHT_ID] = mydata->my_right;
mydata->message[mydata->tail].data[LEFT_ID] = mydata->my_left;
mydata->message[mydata->tail].data[RECEIVER] = mydata->my_right;
mydata->message[mydata->tail].data[SENDER] = mydata->my_id;
mydata->message[mydata->tail].data[STATE] = mydata->state;
mydata->message[mydata->tail].data[LEADER] = mydata->my_leader;
mydata->message[mydata->tail].type = NORMAL;
mydata->message[mydata->tail].crc = message_crc(&mydata->message[mydata->tail]);
mydata->tail++;
mydata->tail = mydata->tail % QUEUE;
return 1;
}
return 0;
}
void elected(uint8_t *payload)
{
mydata->isactive = 0;
if(mydata->my_id == payload[LEADER])
{
mydata->green = 0;
mydata->blue = 0;
mydata->red = 1;
}
else
{
mydata->sent_elected = 1;
mydata->red = 0;
mydata->blue=1;
}
#ifdef SIMULATOR
printf("%d Receives Elected %d ", mydata->my_id, payload[LEADER]);
#endif
}
void electing(uint8_t *payload)
{
#ifdef SIMULATOR
printf("%d Receives Election %d ", mydata->my_id, payload[LEADER]);
#endif
if(mydata->my_id == payload[LEADER])
{
//mydata->elected_id = payload[current_id];
mydata->blue=0;
mydata->red = 1;
mydata->sent_elected = 1;
#ifdef SIMULATOR
printf("%d Leader Elected %d ", mydata->my_id, payload[LEADER]);
#endif
}
else if(mydata->my_leader >payload[LEADER])
{
mydata->my_leader = payload[LEADER];
mydata->sent_election = 1;
mydata->red = 0;
mydata->blue = 1;
}
else
{
//send_election(mydata->elected_id);
if (mydata->isactive == 0)
{
mydata->sent_election = 1;
}
}
}
void recv_sharing(uint8_t *payload, uint8_t distance)
{
if (payload[ID] == mydata->my_id || payload[ID] == 0 || !in_interval(distance) ) return;
uint8_t i = exists_nearest_neighbor(payload[ID]);
if (i >= mydata->num_neighbors) // The id has never received
{
if (mydata->num_neighbors < MAX_NUM_NEIGHBORS)
{
i = mydata->num_neighbors;
mydata->num_neighbors++;
mydata->nearest_neighbors[i].num = 0;
}
}
mydata->nearest_neighbors[i].counter = 0; // added for reseting counter
mydata->nearest_neighbors[i].id = payload[ID];
mydata->nearest_neighbors[i].right_id = payload[RIGHT_ID];
mydata->nearest_neighbors[i].left_id = payload[LEFT_ID];
mydata->nearest_neighbors[i].state = payload[STATE];
mydata->nearest_neighbors[i].distance = distance;
if (payload[STATE] == AUTONOMOUS)
{
mydata->nearest_neighbors[i].num++;
mydata->nearest_neighbors[i].num_cooperative = 0;
}
else
{
mydata->nearest_neighbors[i].num_cooperative++;
mydata->nearest_neighbors[i].num = 0;
}
}
void recv_joining(uint8_t *payload)
{
if (payload[ID] == mydata->my_id) return;
if (payload[RIGHT] == mydata->my_id) // && payload[LEFT] == my_left)
{
mydata->my_right = payload[ID];
mydata->state = COOPERATIVE;
}
if (payload[LEFT] == mydata->my_id) // && payload[RIGHT] == my_right)
{
mydata->my_left = payload[ID];
mydata-> state = COOPERATIVE;
}
if (mydata->num_neighbors == 1 && payload[LEFT] == mydata->my_id)
{
mydata->my_left = mydata->my_right = payload[ID];
mydata->state = COOPERATIVE;
}
if (mydata-> state == COOPERATIVE)
{
mydata->send_token = mydata->now + TOKEN_TIME;
}
}
void recv_move(uint8_t *payload)
{
#ifdef SIMULATOR
printf("%d Receives move %d %d %d ", mydata->my_id, payload[MSG], mydata->my_id, payload[RECEIVER]);
#endif
if (mydata->my_id == payload[RECEIVER])
{
mydata->token = 1;
mydata->blue = 0;
mydata->send_token = mydata->now + TOKEN_TIME * 4.0;
}
/* else if (my_id == payload[SENDER])
{
mydata->motion_state = STOP;
}
else
{
mydata->msg.data[MSG] = payload[MSG];
mydata->msg.data[ID] = mydata->my_id;
mydata->msg.data[RECEIVER] = payload[RECEIVER];
mydata->msg.data[SENDER] = payload[SENDER];
mydata->msg.type = NORMAL;
mydata->msg.crc = message_crc(&msg);
mydata->message_sent = 0;
} */
}
void message_rx(message_t *m, distance_measurement_t *d)
{
uint8_t dist = estimate_distance(d);
if (m->type == NORMAL && m->data[MSG] !=NULL_MSG)
{
#ifdef SIMULATOR
//printf("%d Receives %d %d ", mydata->my_id, m->data[MSG], m->data[RECEIVER]);
#endif
recv_sharing(m->data, dist);
switch (m->data[MSG])
{
case JOIN:
recv_joining(m->data);
break;
case MOVE:
recv_move(m->data);
break;
case ELECTING:
if (mydata->my_left == m->data[ID])
electing(m->data);
break;
case ELECTED:
if (mydata->my_left == m->data[ID])
elected(m->data);
break;
//case ELECTED:
//elected(m->data);
}
}
}
/**********************************/
/**********************************/
void send_joining()
{
uint8_t i;
/* precondition */
if (mydata->state == AUTONOMOUS && is_stabilized() && !isQueueFull())
{
i = get_nearest_two_neighbors();
if (i < mydata->num_neighbors && mydata->message_sent == 1)
{
// effect:
mydata->state = COOPERATIVE;
mydata->my_right = mydata->nearest_neighbors[i].right_id;
mydata->my_left = mydata->nearest_neighbors[i].id;
enqueue_message(JOIN);
mydata->send_token = mydata->now + TOKEN_TIME;
mydata->sent_election = 1;
#ifdef SIMULATOR
printf("Sending Joining %d right=%d left=%d ", mydata->my_id, mydata->my_right, mydata->my_left);
#endif
}
}
}
void send_sharing()
{
// Precondition
if (mydata->now >= mydata->nextShareSending && !isQueueFull())
{
// Sending
enqueue_message(SHARE);
// effect:
mydata->nextShareSending = mydata->now + SHARING_TIME;
}
}
void send_election()
{
if (mydata->sent_election &&!isQueueFull())
{
enqueue_message(ELECTING);
mydata->sent_election = 0;
mydata->isactive = 1;
#ifdef SIMULATOR
printf("Sending Election %d right=%d left=%d ", mydata->my_id, mydata->my_right, mydata->my_left);
#endif
}
}
void send_elected()
{
if (mydata->sent_elected &&!isQueueFull())
{
enqueue_message(ELECTED);
mydata->sent_elected = 0;
}
}
void send_move()
{
// Precondition:
if (mydata->state == COOPERATIVE && mydata->token )
{
mydata->send_token = mydata->now + TOKEN_TIME;
}
if (mydata->state == COOPERATIVE && !isQueueFull() && mydata->token && mydata->send_token <= mydata->now)
{
// Sending
enqueue_message(MOVE);
mydata->token = 0;
mydata->blue = 0;
// effect:
//electing()
}
}
void neighborCounter(){
for (uint8_t i=0; i
{
mydata->nearest_neighbors[i].counter++; //increment all neighbour's counter for every node
}
}
void reset(){
if(mydata->failureDetectedFlag==1){
#ifdef SIMULATOR
printf("Calling Setup for %d ",mydata->my_id);
#endif
mydata->failureDetectedFlag=0;
mydata-> my_left = mydata->my_right = mydata->my_id;
}
}
void failureDetector(){
for (uint8_t i=0; i
{
if(mydata->nearest_neighbors[i].counter > 80){
#ifdef SIMULATOR
printf(" ************************************************ ");
printf("failure Detected ");
#endif
mydata->failureDetectedFlag = 1;
mydata->state = AUTONOMOUS;
mydata->nearest_neighbors[i].counter =0;
for(uint8_t j=i;j
mydata->nearest_neighbors[j]=mydata->nearest_neighbors[j+1];//shifting nearest_neighbor entries
set_color(RGB(mydata->red, mydata->green, mydata->blue));
}
mydata->num_neighbors--; //decrementing total number of neighbors
}
}
reset();
}
void setState(){
if(mydata->num_neighbors==0){
mydata->state = AUTONOMOUS;
set_color(RGB(0,0,0));
} else if(mydata->state==COOPERATIVE){
set_color(RGB(mydata->red, mydata->green, mydata->blue));
}
}
void move(uint8_t tick)
{
// Precondition:
if (mydata->motion_state == ACTIVE && mydata->state == COOPERATIVE)
{
/* if (mydata->time_active == mydata->move_motion[mydata->move_state].time)
{
// Effect:
mydata->green = 1;
mydata->move_state++;
if (mydata->move_state == 3)
{
mydata->send_token = 1;
send_move();
#ifdef SIMULATOR
printf("Sending Move %d ", mydata->my_id);
#endif
mydata->motion_state = STOP;
return;
}
mydata->time_active = 0;
}
set_motion(mydata->move_motion[mydata->move_state].motion);
mydata->time_active++;
*/
}
else
{
mydata->green = 0;
set_motion(STOP);
}
}
void loop()
{
delay(30);
//send_move();
send_joining();
send_sharing();
send_election();
send_elected();
//move(mydata->now);
set_color(RGB(mydata->red, mydata->green, mydata->blue));
mydata->now++;
neighborCounter();
failureDetector();
setState();
#ifdef SIMULATOR
printf("My id : %d Num neighbors :%d ", mydata->my_id, mydata->num_neighbors);
#endif
}
message_t *message_tx()
{
if (mydata->tail != mydata->head) // Queue is not empty
{
#ifdef SIMULATOR
//printf("%d, Sending %d %d ", mydata->my_id, mydata->message[mydata->head].data[MSG] , mydata->message[mydata->head].data[RECEIVER]);
#endif
return &mydata->message[mydata->head];
}
return &mydata->nullmessage;
}
void message_tx_success() {
if (mydata->tail != mydata->head) { // Queue is not empty
#ifdef SIMULATOR
//printf("%d Sent %d, %d ", mydata->my_id, mydata->message[mydata->head].data[MSG], mydata->message[mydata->head].data[RECEIVER]);
#endif
if (mydata->copies == 2)
{
mydata->head++;
mydata->copies = 0;
mydata->head = mydata->head % QUEUE;
}
else
{
mydata->copies++;
}
}
}
void setup() {
rand_seed(rand_hard());
mydata->my_id = rand_soft();
mydata->state = AUTONOMOUS;
mydata->my_left = mydata->my_right = mydata->my_id;
mydata->num_neighbors = 0;
mydata->message_sent = 0,
mydata->now = 0,
mydata->nextShareSending = SHARING_TIME,
mydata->cur_motion = STOP;
mydata->motion_state = STOP;
mydata->time_active = 0;
mydata->move_state = 0;
mydata->move_motion[0].motion = LEFT;
mydata->move_motion[0].motion = 3;
mydata->move_motion[1].motion = RIGHT;
mydata->move_motion[1].motion = 5;
mydata->move_motion[0].motion = LEFT;
mydata->move_motion[0].motion = 2;
mydata->red = 0,
mydata->green = 0,
mydata->blue = 0,
mydata->send_token = 0;
mydata->nullmessage.data[MSG] = NULL_MSG;
mydata->nullmessage.crc = message_crc(&mydata->nullmessage);
mydata->failureDetectedFlag =0;
mydata->token = rand_soft() < 128 ? 1 : 0;
mydata->blue = 1;
mydata->head = 0;
mydata->tail = 0;
mydata->copies = 0;
mydata->sent_election = 0;
mydata->sent_elected = 0;
mydata->isactive = 0;
mydata->my_leader = mydata->my_id;
#ifdef SIMULATOR
printf("Initializing %d %d ", mydata->my_id, mydata->token);
#endif
mydata->message_sent = 1;
}
#ifdef SIMULATOR
/* provide a text string for the simulator status bar about this bot */
static char botinfo_buffer[10000];
char *cb_botinfo(void)
{
char *p = botinfo_buffer;
p += sprintf (p, "ID: %d ", kilo_uid);
if (mydata->state == COOPERATIVE)
p += sprintf (p, "State: COOPERATIVE ");
if (mydata->state == AUTONOMOUS)
p += sprintf (p, "State: AUTONOMOUS ");
return botinfo_buffer;
}
#endif
int main() {
kilo_init();
kilo_message_tx = message_tx;
kilo_message_tx_success = message_tx_success;
kilo_message_rx = message_rx;
kilo_start(setup, loop);
return 0;
}
***************************************************************************************************************************************************************************************
"le.h"
#define MAX_NUM_NEIGHBORS 10
#define SHARING_TIME 100
#define TOKEN_TIME 103
//PAYLOAD
#define MSG 0
#define ID 1
#define RIGHT_ID 2
#define LEFT_ID 3
#define STATE 4
#define RECEIVER 5
#define SENDER 6
#define LEADER 7
#define ACTIVE 0
#define QUEUE 2
#ifndef M_PI
#define M_PI 3.141592653589793238462643383279502884197169399375105820974944
#endif
typedef enum { NULL_MSG,
SHARE,
JOIN,
LEAVE,
MOVE,
ELECTING,
ELECTED
} message_type; // MESSAGES
typedef enum {
AUTONOMOUS,
COOPERATIVE
} robot_state; // STATE
// declare motion variable type
typedef enum {
STOP,
FORWARD,
LEFT,
RIGHT
} motion_t;
typedef struct{
uint8_t id;
uint8_t right_id;
uint8_t left_id;
robot_state state;
uint8_t distance;
uint8_t counter;
uint8_t num;
uint8_t num_cooperative;
} nearest_neighbor_t;
typedef struct {
uint8_t motion;
uint8_t time;
} motion_time_t;
typedef struct
{
uint8_t my_id;
uint8_t my_right;
uint8_t my_left;
message_t message[QUEUE];
message_t nullmessage;
robot_state state;
uint8_t failureDetectedFlag;
uint8_t num_neighbors;
uint8_t message_sent;
uint16_t now;
uint16_t nextShareSending;
uint8_t cur_motion;
uint8_t motion_state;
uint8_t time_active;
uint8_t move_state;
nearest_neighbor_t nearest_neighbors[MAX_NUM_NEIGHBORS];
motion_time_t move_motion[3];
char send_token;
uint8_t green;
uint8_t red;
uint8_t blue;
int8_t token;
int8_t head, tail;
int8_t copies;
uint8_t my_leader;
int8_t sent_election;
int8_t sent_elected;
int8_t isactive;
} USERDATA;
***************************************************************************************************************************************************************************************
"start_positions.json"
{ "bot_states": [ { "ID": 0, "direction": 5.7269688373804088, "state": {}, "x_position": 0.900863330484285, "y_position": 0.4895537075976648 }, { "ID": 1, "direction": -132.14180267595034, "state": {}, "x_position": 50.053018924909047, "y_position": 0.928440210936703 }, { "ID": 2, "direction": 132.14180267595034, "state": {}, "x_position": 100.053018924909047, "y_position": 0.928440210936703 },
{ "ID": 3, "direction": 132.14180267595034, "state": {}, "x_position": -20.053018924909047, "y_position": 50.928440210936703 }, { "ID": 4, "direction": 132.14180267595034, "state": {}, "x_position": 0.053018924909047, "y_position": 100.928440210936703 },
{ "ID": 5, "direction": 132.14180267595034, "state": {}, "x_position": 50.053018924909047, "y_position": 120.928440210936703 },
{ "ID": 6, "direction": 132.14180267595034, "state": {}, "x_position": 100.053018924909047, "y_position": 100.928440210936703 }, { "ID": 7, "direction": 132.14180267595034, "state": {}, "x_position": 120.053018924909047, "y_position": 50.928440210936703 } ], "ticks": 7680 }
***************************************************************************************************************************************************************
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Learning MySQL Get A Handle On Your Data
Authors: Seyed M M Tahaghoghi
1st Edition
0596529465, 9780596529468
